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

#if ENABLE(DFG_JIT)

#include "DFGBasicBlockInlines.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGPhase.h"
#include "DFGValidate.h"
#include "JSCInlines.h"

namespace JSC { namespace DFG {

class CFGSimplificationPhase : public Phase {
public:
    CFGSimplificationPhase(Graph& graph)
        : Phase(graph, "CFG simplification")
    {
    }

    bool canMergeBlocks(BasicBlock* block, BasicBlock* targetBlock)
    {
        return targetBlock->predecessors.size() == 1 && targetBlock != block;
    }
    
    bool run()
    {
        // FIXME: We should make this work in SSA. https://bugs.webkit.org/show_bug.cgi?id=148260
        DFG_ASSERT(m_graph, nullptr, m_graph.m_form != SSA);
        
        const bool extremeLogging = false;

        bool outerChanged = false;
        bool innerChanged;
        
        do {
            innerChanged = false;
            for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
                BasicBlock* block = m_graph.block(blockIndex);
                if (!block)
                    continue;
                ASSERT(block->isReachable);

                auto canMergeWithBlock = [&] (BasicBlock* targetBlock) {
                    return canMergeBlocks(block, targetBlock);
                };
            
                switch (block->terminal()->op()) {
                case Jump: {
                    // Successor with one predecessor -> merge.
                    if (canMergeWithBlock(block->successor(0))) {
                        ASSERT(block->successor(0)->predecessors[0] == block);
                        if (extremeLogging)
                            m_graph.dump();
                        m_graph.dethread();
                        mergeBlocks(block, block->successor(0), noBlocks());
                        innerChanged = outerChanged = true;
                        break;
                    }
                
                    // FIXME: Block only has a jump -> remove. This is tricky though because of
                    // liveness. What we really want is to slam in a phantom at the end of the
                    // block, after the terminal. But we can't right now. :-(
                    // Idea: what if I slam the ghosties into my successor? Nope, that's
                    // suboptimal, because if my successor has multiple predecessors then we'll
                    // be keeping alive things on other predecessor edges unnecessarily.
                    // What we really need is the notion of end-of-block ghosties!
                    // FIXME: Allow putting phantoms after terminals.
                    // https://bugs.webkit.org/show_bug.cgi?id=126778
                    break;
                }
                
                case Branch: {
                    // Branch on constant -> jettison the not-taken block and merge.
                    if (isKnownDirection(block->cfaBranchDirection)) {
                        bool condition = branchCondition(block->cfaBranchDirection);
                        BasicBlock* targetBlock = block->successorForCondition(condition);
                        BasicBlock* jettisonedBlock = block->successorForCondition(!condition);
                        if (canMergeWithBlock(targetBlock)) {
                            if (extremeLogging)
                                m_graph.dump();
                            m_graph.dethread();
                            if (targetBlock == jettisonedBlock)
                                mergeBlocks(block, targetBlock, noBlocks());
                            else
                                mergeBlocks(block, targetBlock, oneBlock(jettisonedBlock));
                        } else {
                            if (extremeLogging)
                                m_graph.dump();
                            m_graph.dethread();
                            
                            Node* terminal = block->terminal();
                            ASSERT(terminal->isTerminal());
                            NodeOrigin boundaryNodeOrigin = terminal->origin;

                            if (targetBlock != jettisonedBlock)
                                jettisonBlock(block, jettisonedBlock, boundaryNodeOrigin);

                            block->replaceTerminal(
                                m_graph, SpecNone, Jump, boundaryNodeOrigin,
                                OpInfo(targetBlock));
                            
                            ASSERT(block->terminal());
                        
                        }
                        innerChanged = outerChanged = true;
                        break;
                    }
                    
                    if (block->successor(0) == block->successor(1)) {
                        convertToJump(block, block->successor(0));
                        innerChanged = outerChanged = true;
                        break;
                    }

                    // Branch to same destination -> jump.
                    // FIXME: this will currently not be hit because of the lack of jump-only
                    // block simplification.
                    
                    break;
                }
                    
                case Switch: {
                    SwitchData* data = block->terminal()->switchData();
                    
                    // Prune out cases that end up jumping to default.
                    for (unsigned i = 0; i < data->cases.size(); ++i) {
                        if (data->cases[i].target.block == data->fallThrough.block) {
                            data->fallThrough.count += data->cases[i].target.count;
                            data->cases[i--] = data->cases.last();
                            data->cases.removeLast();
                        }
                    }
                    
                    // If there are no cases other than default then this turns
                    // into a jump.
                    if (data->cases.isEmpty()) {
                        convertToJump(block, data->fallThrough.block);
                        innerChanged = outerChanged = true;
                        break;
                    }
                    
                    // Switch on constant -> jettison all other targets and merge.
                    Node* terminal = block->terminal();
                    if (terminal->child1()->hasConstant()) {
                        FrozenValue* value = terminal->child1()->constant();
                        TriState found = FalseTriState;
                        BasicBlock* targetBlock = 0;
                        for (unsigned i = data->cases.size(); found == FalseTriState && i--;) {
                            found = data->cases[i].value.strictEqual(value);
                            if (found == TrueTriState)
                                targetBlock = data->cases[i].target.block;
                        }
                        
                        if (found == MixedTriState)
                            break;
                        if (found == FalseTriState)
                            targetBlock = data->fallThrough.block;
                        ASSERT(targetBlock);
                        
                        Vector<BasicBlock*, 1> jettisonedBlocks;
                        for (BasicBlock* successor : terminal->successors()) {
                            if (successor != targetBlock && !jettisonedBlocks.contains(successor))
                                jettisonedBlocks.append(successor);
                        }
                        
                        if (canMergeWithBlock(targetBlock)) {
                            if (extremeLogging)
                                m_graph.dump();
                            m_graph.dethread();
                            
                            mergeBlocks(block, targetBlock, jettisonedBlocks);
                        } else {
                            if (extremeLogging)
                                m_graph.dump();
                            m_graph.dethread();
                            
                            NodeOrigin boundaryNodeOrigin = terminal->origin;

                            for (unsigned i = jettisonedBlocks.size(); i--;)
                                jettisonBlock(block, jettisonedBlocks[i], boundaryNodeOrigin);
                            
                            block->replaceTerminal(
                                m_graph, SpecNone, Jump, boundaryNodeOrigin, OpInfo(targetBlock));
                        }
                        innerChanged = outerChanged = true;
                        break;
                    }
                    break;
                }
                    
                default:
                    break;
                }
            }
            
            if (innerChanged) {
                // Here's the reason for this pass:
                // Blocks: A, B, C, D, E, F
                // A -> B, C
                // B -> F
                // C -> D, E
                // D -> F
                // E -> F
                //
                // Assume that A's branch is determined to go to B. Then the rest of this phase
                // is smart enough to simplify down to:
                // A -> B
                // B -> F
                // C -> D, E
                // D -> F
                // E -> F
                //
                // We will also merge A and B. But then we don't have any other mechanism to
                // remove D, E as predecessors for F. Worse, the rest of this phase does not
                // know how to fix the Phi functions of F to ensure that they no longer refer
                // to variables in D, E. In general, we need a way to handle Phi simplification
                // upon:
                // 1) Removal of a predecessor due to branch simplification. The branch
                //    simplifier already does that.
                // 2) Invalidation of a predecessor because said predecessor was rendered
                //    unreachable. We do this here.
                //
                // This implies that when a block is unreachable, we must inspect its
                // successors' Phi functions to remove any references from them into the
                // removed block.
                
                m_graph.invalidateCFG();
                m_graph.resetReachability();
                m_graph.killUnreachableBlocks();
            }
            
            if (Options::validateGraphAtEachPhase())
                validate();
        } while (innerChanged);
        
        return outerChanged;
    }

private:
    void convertToJump(BasicBlock* block, BasicBlock* targetBlock)
    {
        ASSERT(targetBlock);
        ASSERT(targetBlock->isReachable);
        if (canMergeBlocks(block, targetBlock)) {
            m_graph.dethread();
            mergeBlocks(block, targetBlock, noBlocks());
        } else {
            Node* branch = block->terminal();
            ASSERT(branch->op() == Branch || branch->op() == Switch);

            block->replaceTerminal(
                m_graph, SpecNone, Jump, branch->origin, OpInfo(targetBlock));
        }
    }
    
    void keepOperandAlive(BasicBlock* block, BasicBlock* jettisonedBlock, NodeOrigin nodeOrigin, VirtualRegister operand)
    {
        Node* livenessNode = jettisonedBlock->variablesAtHead.operand(operand);
        if (!livenessNode)
            return;
        NodeType nodeType;
        if (livenessNode->flags() & NodeIsFlushed)
            nodeType = Flush;
        else {
            // This seems like it shouldn't be necessary because we could just rematerialize
            // PhantomLocals or something similar using bytecode liveness. However, in ThreadedCPS, it's
            // worth the sanity to maintain this eagerly. See
            // https://bugs.webkit.org/show_bug.cgi?id=144086
            nodeType = PhantomLocal;
        }
        block->appendNode(
            m_graph, SpecNone, nodeType, nodeOrigin, 
            OpInfo(livenessNode->variableAccessData()));
    }
    
    void jettisonBlock(BasicBlock* block, BasicBlock* jettisonedBlock, NodeOrigin boundaryNodeOrigin)
    {
        for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i)
            keepOperandAlive(block, jettisonedBlock, boundaryNodeOrigin, virtualRegisterForArgument(i));
        for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i)
            keepOperandAlive(block, jettisonedBlock, boundaryNodeOrigin, virtualRegisterForLocal(i));
        
        fixJettisonedPredecessors(block, jettisonedBlock);
    }
    
    void fixJettisonedPredecessors(BasicBlock* block, BasicBlock* jettisonedBlock)
    {
        jettisonedBlock->removePredecessor(block);
    }

    Vector<BasicBlock*, 1> noBlocks()
    {
        return Vector<BasicBlock*, 1>();
    }
    
    Vector<BasicBlock*, 1> oneBlock(BasicBlock* block)
    {
        Vector<BasicBlock*, 1> result;
        result.append(block);
        return result;
    }
    
    void mergeBlocks(
        BasicBlock* firstBlock, BasicBlock* secondBlock,
        Vector<BasicBlock*, 1> jettisonedBlocks)
    {
        RELEASE_ASSERT(canMergeBlocks(firstBlock, secondBlock));
        // This will add all of the nodes in secondBlock to firstBlock, but in so doing
        // it will also ensure that any GetLocals from the second block that refer to
        // SetLocals in the first block are relinked. If jettisonedBlock is not NoBlock,
        // then Phantoms are inserted for anything that the jettisonedBlock would have
        // kept alive.
        
        // Remove the terminal of firstBlock since we don't need it anymore. Well, we don't
        // really remove it; we actually turn it into a check.
        Node* terminal = firstBlock->terminal();
        ASSERT(terminal->isTerminal());
        NodeOrigin boundaryNodeOrigin = terminal->origin;
        terminal->remove(m_graph);
        ASSERT(terminal->refCount() == 1);
        
        for (unsigned i = jettisonedBlocks.size(); i--;) {
            BasicBlock* jettisonedBlock = jettisonedBlocks[i];
            
            // Time to insert ghosties for things that need to be kept alive in case we OSR
            // exit prior to hitting the firstBlock's terminal, and end up going down a
            // different path than secondBlock.
            
            for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i)
                keepOperandAlive(firstBlock, jettisonedBlock, boundaryNodeOrigin, virtualRegisterForArgument(i));
            for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i)
                keepOperandAlive(firstBlock, jettisonedBlock, boundaryNodeOrigin, virtualRegisterForLocal(i));
        }
        
        for (size_t i = 0; i < secondBlock->phis.size(); ++i)
            firstBlock->phis.append(secondBlock->phis[i]);

        for (size_t i = 0; i < secondBlock->size(); ++i)
            firstBlock->append(secondBlock->at(i));
        
        ASSERT(firstBlock->terminal()->isTerminal());
        
        // Fix the predecessors of my new successors. This is tricky, since we are going to reset
        // all predecessors anyway due to reachability analysis. But we need to fix the
        // predecessors eagerly to ensure that we know what they are in case the next block we
        // consider in this phase wishes to query the predecessors of one of the blocks we
        // affected.
        for (unsigned i = firstBlock->numSuccessors(); i--;) {
            BasicBlock* successor = firstBlock->successor(i);
            for (unsigned j = 0; j < successor->predecessors.size(); ++j) {
                if (successor->predecessors[j] == secondBlock)
                    successor->predecessors[j] = firstBlock;
            }
        }
        
        // Fix the predecessors of my former successors. Again, we'd rather not do this, but it's
        // an unfortunate necessity. See above comment.
        for (unsigned i = jettisonedBlocks.size(); i--;)
            fixJettisonedPredecessors(firstBlock, jettisonedBlocks[i]);
        
        firstBlock->valuesAtTail = secondBlock->valuesAtTail;
        firstBlock->cfaBranchDirection = secondBlock->cfaBranchDirection;
        
        m_graph.killBlock(secondBlock);
    }
};

bool performCFGSimplification(Graph& graph)
{
    return runPhase<CFGSimplificationPhase>(graph);
}

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)