path: root/Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp

/*
 * Copyright (C) 2012, 2013 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 "DFGAbstractState.h"
#include "DFGBasicBlockInlines.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGPhase.h"
#include "DFGValidate.h"
#include "Operations.h"

namespace JSC { namespace DFG {

class CFGSimplificationPhase : public Phase {
public:
    CFGSimplificationPhase(Graph& graph)
        : Phase(graph, "CFG simplification")
    {
    }
    
    bool run()
    {
        const bool extremeLogging = false;

        bool outerChanged = false;
        bool innerChanged;
        
        do {
            innerChanged = false;
            for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
                BasicBlock* block = m_graph.m_blocks[blockIndex].get();
                if (!block)
                    continue;
                ASSERT(block->isReachable);
            
                switch (block->last()->op()) {
                case Jump: {
                    // Successor with one predecessor -> merge.
                    if (m_graph.m_blocks[m_graph.successor(block, 0)]->m_predecessors.size() == 1) {
                        ASSERT(m_graph.m_blocks[m_graph.successor(block, 0)]->m_predecessors[0]
                               == blockIndex);
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
                        dataLogF("CFGSimplify: Jump merge on Block #%u to Block #%u.\n",
                                blockIndex, m_graph.successor(block, 0));
#endif
                        if (extremeLogging)
                            m_graph.dump();
                        m_graph.dethread();
                        mergeBlocks(blockIndex, m_graph.successor(block, 0), NoBlock);
                        innerChanged = outerChanged = true;
                        break;
                    } else {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
                        dataLogF("Not jump merging on Block #%u to Block #%u because predecessors = ",
                                blockIndex, m_graph.successor(block, 0));
                        for (unsigned i = 0; i < m_graph.m_blocks[m_graph.successor(block, 0)]->m_predecessors.size(); ++i) {
                            if (i)
                                dataLogF(", ");
                            dataLogF("#%u", m_graph.m_blocks[m_graph.successor(block, 0)]->m_predecessors[i]);
                        }
                        dataLogF(".\n");
#endif
                    }
                
                    // 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!
                    break;
                }
                
                case Branch: {
                    // Branch on constant -> jettison the not-taken block and merge.
                    if (isKnownDirection(block->cfaBranchDirection)) {
                        bool condition = branchCondition(block->cfaBranchDirection);
                        BasicBlock* targetBlock = m_graph.m_blocks[
                            m_graph.successorForCondition(block, condition)].get();
                        if (targetBlock->m_predecessors.size() == 1) {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
                            dataLogF("CFGSimplify: Known condition (%s) branch merge on Block #%u to Block #%u, jettisoning Block #%u.\n",
                                    condition ? "true" : "false",
                                    blockIndex, m_graph.successorForCondition(block, condition),
                                    m_graph.successorForCondition(block, !condition));
#endif
                            if (extremeLogging)
                                m_graph.dump();
                            m_graph.dethread();
                            mergeBlocks(
                                blockIndex,
                                m_graph.successorForCondition(block, condition),
                                m_graph.successorForCondition(block, !condition));
                        } else {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
                            dataLogF("CFGSimplify: Known condition (%s) branch->jump conversion on Block #%u to Block #%u, jettisoning Block #%u.\n",
                                    condition ? "true" : "false",
                                    blockIndex, m_graph.successorForCondition(block, condition),
                                    m_graph.successorForCondition(block, !condition));
#endif
                            if (extremeLogging)
                                m_graph.dump();
                            m_graph.dethread();
                            BlockIndex takenBlockIndex = m_graph.successorForCondition(block, condition);
                            BlockIndex notTakenBlockIndex = m_graph.successorForCondition(block, !condition);
                        
                            ASSERT(block->last()->isTerminal());
                            CodeOrigin boundaryCodeOrigin = block->last()->codeOrigin;
                            block->last()->convertToPhantom();
                            ASSERT(block->last()->refCount() == 1);
                        
                            jettisonBlock(blockIndex, notTakenBlockIndex, boundaryCodeOrigin);
                        
                            block->appendNode(
                                m_graph, SpecNone, Jump, boundaryCodeOrigin,
                                OpInfo(takenBlockIndex));
                        }
                        innerChanged = outerChanged = true;
                        break;
                    }
                    
                    if (m_graph.successor(block, 0) == m_graph.successor(block, 1)) {
                        BlockIndex targetBlockIndex = m_graph.successor(block, 0);
                        BasicBlock* targetBlock = m_graph.m_blocks[targetBlockIndex].get();
                        ASSERT(targetBlock);
                        ASSERT(targetBlock->isReachable);
                        if (targetBlock->m_predecessors.size() == 1) {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
                            dataLogF("CFGSimplify: Branch to same successor merge on Block #%u to Block #%u.\n",
                                    blockIndex, targetBlockIndex);
#endif
                            m_graph.dethread();
                            mergeBlocks(blockIndex, targetBlockIndex, NoBlock);
                        } else {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
                            dataLogF("CFGSimplify: Branch->jump conversion to same successor on Block #%u to Block #%u.\n",
                                    blockIndex, targetBlockIndex);
#endif
                            Node* branch = block->last();
                            ASSERT(branch->isTerminal());
                            ASSERT(branch->op() == Branch);
                            branch->convertToPhantom();
                            ASSERT(branch->refCount() == 1);
                            
                            block->appendNode(
                                m_graph, SpecNone, Jump, branch->codeOrigin,
                                OpInfo(targetBlockIndex));
                        }
                        innerChanged = outerChanged = true;
                        break;
                    }
                    
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
                    dataLogF("Not branch simplifying on Block #%u because the successors differ and the condition is not known.\n",
                            blockIndex);
#endif
                
                    // Branch to same destination -> jump.
                    // FIXME: this will currently not be hit because of the lack of jump-only
                    // block simplification.
                    
                    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.resetReachability();

                for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
                    BasicBlock* block = m_graph.m_blocks[blockIndex].get();
                    if (!block)
                        continue;
                    if (block->isReachable)
                        continue;
                    
                    killUnreachable(blockIndex);
                }
            }
            
            if (Options::validateGraphAtEachPhase())
                validate(m_graph);
        } while (innerChanged);
        
        return outerChanged;
    }

private:
    void killUnreachable(BlockIndex blockIndex)
    {
        BasicBlock* block = m_graph.m_blocks[blockIndex].get();
        
        ASSERT(block);
        ASSERT(!block->isReachable);
        
        for (unsigned phiIndex = block->phis.size(); phiIndex--;)
            m_graph.m_allocator.free(block->phis[phiIndex]);
        for (unsigned nodeIndex = block->size(); nodeIndex--;)
            m_graph.m_allocator.free(block->at(nodeIndex));
        
        m_graph.m_blocks[blockIndex].clear();
    }
    
    void keepOperandAlive(BasicBlock* block, BasicBlock* jettisonedBlock, CodeOrigin codeOrigin, int operand)
    {
        Node* livenessNode = jettisonedBlock->variablesAtHead.operand(operand);
        if (!livenessNode)
            return;
        if (livenessNode->variableAccessData()->isCaptured())
            return;
        block->appendNode(
            m_graph, SpecNone, PhantomLocal, codeOrigin, 
            OpInfo(livenessNode->variableAccessData()));
    }
    
    void jettisonBlock(BlockIndex blockIndex, BlockIndex jettisonedBlockIndex, CodeOrigin boundaryCodeOrigin)
    {
        BasicBlock* block = m_graph.m_blocks[blockIndex].get();
        BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get();
        
        for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i)
            keepOperandAlive(block, jettisonedBlock, boundaryCodeOrigin, argumentToOperand(i));
        for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i)
            keepOperandAlive(block, jettisonedBlock, boundaryCodeOrigin, i);
        
        fixJettisonedPredecessors(blockIndex, jettisonedBlockIndex);
    }
    
    void fixJettisonedPredecessors(BlockIndex blockIndex, BlockIndex jettisonedBlockIndex)
    {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        dataLogF("Fixing predecessors and phis due to jettison of Block #%u from Block #%u.\n",
                jettisonedBlockIndex, blockIndex);
#endif
        BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get();
        for (unsigned i = 0; i < jettisonedBlock->m_predecessors.size(); ++i) {
            if (jettisonedBlock->m_predecessors[i] != blockIndex)
                continue;
            jettisonedBlock->m_predecessors[i] = jettisonedBlock->m_predecessors.last();
            jettisonedBlock->m_predecessors.removeLast();
            break;
        }
    }
    
    void mergeBlocks(
        BlockIndex firstBlockIndex, BlockIndex secondBlockIndex, BlockIndex jettisonedBlockIndex)
    {
        // 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.
        
        BasicBlock* firstBlock = m_graph.m_blocks[firstBlockIndex].get();
        BasicBlock* secondBlock = m_graph.m_blocks[secondBlockIndex].get();
        
        // 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 Phantom.
        ASSERT(firstBlock->last()->isTerminal());
        CodeOrigin boundaryCodeOrigin = firstBlock->last()->codeOrigin;
        firstBlock->last()->convertToPhantom();
        ASSERT(firstBlock->last()->refCount() == 1);
        
        if (jettisonedBlockIndex != NoBlock) {
            BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get();
            
            // 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, boundaryCodeOrigin, argumentToOperand(i));
            for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i)
                keepOperandAlive(firstBlock, jettisonedBlock, boundaryCodeOrigin, 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->last()->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 = m_graph.numSuccessors(firstBlock); i--;) {
            BasicBlock* successor = m_graph.m_blocks[m_graph.successor(firstBlock, i)].get();
            for (unsigned j = 0; j < successor->m_predecessors.size(); ++j) {
                if (successor->m_predecessors[j] == secondBlockIndex)
                    successor->m_predecessors[j] = firstBlockIndex;
            }
        }
        
        // Fix the predecessors of my former successors. Again, we'd rather not do this, but it's
        // an unfortunate necessity. See above comment.
        if (jettisonedBlockIndex != NoBlock)
            fixJettisonedPredecessors(firstBlockIndex, jettisonedBlockIndex);
        
        firstBlock->valuesAtTail = secondBlock->valuesAtTail;
        firstBlock->cfaBranchDirection = secondBlock->cfaBranchDirection;
        
        m_graph.m_blocks[secondBlockIndex].clear();
    }
};

bool performCFGSimplification(Graph& graph)
{
    SamplingRegion samplingRegion("DFG CFG Simplification Phase");
    return runPhase<CFGSimplificationPhase>(graph);
}

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)