/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set ts=8 sts=4 et sw=4 tw=99:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "UnreachableCodeElimination.h"
#include "IonAnalysis.h"
#include "AliasAnalysis.h"
#include "ValueNumbering.h"

using namespace js;
using namespace jit;

bool
UnreachableCodeElimination::analyze()
{
    // The goal of this routine is to eliminate code that is
    // unreachable, either because there is no path from the entry
    // block to the code, or because the path traverses a conditional
    // branch where the condition is a constant (e.g., "if (false) {
    // ... }").  The latter can either appear in the source form or
    // arise due to optimizations.
    //
    // The stategy is straightforward.  The pass begins with a
    // depth-first search.  We set a bit on each basic block that
    // is visited.  If a block terminates in a conditional branch
    // predicated on a constant, we rewrite the block to an unconditional
    // jump and do not visit the now irrelevant basic block.
    //
    // Once the initial DFS is complete, we do a second pass over the
    // blocks to find those that were not reached.  Those blocks are
    // simply removed wholesale.  We must also correct any phis that
    // may be affected..

    // Pass 1: Identify unreachable blocks (if any).
    if (!prunePointlessBranchesAndMarkReachableBlocks())
        return false;

    return removeUnmarkedBlocksAndCleanup();
}

bool
UnreachableCodeElimination::removeUnmarkedBlocks(size_t marked)
{
    marked_ = marked;
    return removeUnmarkedBlocksAndCleanup();
}

bool
UnreachableCodeElimination::removeUnmarkedBlocksAndCleanup()
{
    // Everything is reachable, no work required.
    JS_ASSERT(marked_ <= graph_.numBlocks());
    if (marked_ == graph_.numBlocks()) {
        graph_.unmarkBlocks();
        return true;
    }

    // Pass 2: Remove unmarked blocks (see analyze() above).
    if (!removeUnmarkedBlocksAndClearDominators())
        return false;
    graph_.unmarkBlocks();

    AssertGraphCoherency(graph_);

    IonSpewPass("UCE-mid-point");

    // Pass 3: Recompute dominators and tweak phis.
    BuildDominatorTree(graph_);
    if (redundantPhis_ && !EliminatePhis(mir_, graph_, ConservativeObservability))
        return false;

    // Pass 4: Rerun alias analysis
    if (rerunAliasAnalysis_) {
        AliasAnalysis analysis(mir_, graph_);
        if (!analysis.analyze())
            return false;
    }

    // Pass 5: It's important for optimizations to re-run GVN (and in
    // turn alias analysis) after UCE if we eliminated branches.
    if (rerunAliasAnalysis_ && js_IonOptions.gvn) {
        ValueNumberer gvn(mir_, graph_, js_IonOptions.gvnIsOptimistic);
        if (!gvn.clear() || !gvn.analyze())
            return false;
        IonSpewPass("GVN-after-UCE");
        AssertExtendedGraphCoherency(graph_);

        if (mir_->shouldCancel("GVN-after-UCE"))
            return false;
    }

    return true;
}

bool
UnreachableCodeElimination::enqueue(MBasicBlock *block, BlockList &list)
{
    if (block->isMarked())
        return true;

    block->mark();
    marked_++;
    return list.append(block);
}

MBasicBlock *
UnreachableCodeElimination::optimizableSuccessor(MBasicBlock *block)
{
    // If the last instruction in `block` is a test instruction of a
    // constant value, returns the successor that the branch will
    // always branch to at runtime. Otherwise, returns NULL.

    MControlInstruction *ins = block->lastIns();
    if (!ins->isTest())
        return NULL;

    MTest *testIns = ins->toTest();
    MDefinition *v = testIns->getOperand(0);
    if (!v->isConstant())
        return NULL;

    const Value &val = v->toConstant()->value();
    BranchDirection bdir = ToBoolean(val) ? TRUE_BRANCH : FALSE_BRANCH;
    return testIns->branchSuccessor(bdir);
}

bool
UnreachableCodeElimination::prunePointlessBranchesAndMarkReachableBlocks()
{
    BlockList worklist, optimizableBlocks;

    // Process everything reachable from the start block, ignoring any
    // OSR block.
    if (!enqueue(graph_.entryBlock(), worklist))
        return false;
    while (!worklist.empty()) {
        if (mir_->shouldCancel("Eliminate Unreachable Code"))
            return false;

        MBasicBlock *block = worklist.popCopy();

        // If this block is a test on a constant operand, only enqueue
        // the relevant successor. Also, remember the block for later.
        if (MBasicBlock *succ = optimizableSuccessor(block)) {
            if (!optimizableBlocks.append(block))
                return false;
            if (!enqueue(succ, worklist))
                return false;
        } else {
            // Otherwise just visit all successors.
            for (size_t i = 0; i < block->numSuccessors(); i++) {
                MBasicBlock *succ = block->getSuccessor(i);
                if (!enqueue(succ, worklist))
                    return false;
            }
        }
    }

    // Now, if there is an OSR block, check that all of its successors
    // were reachable (bug 880377). If not, we are in danger of
    // creating a CFG with two disjoint parts, so simply mark all
    // blocks as reachable. This generally occurs when the TI info for
    // stack types is incorrect or incomplete, due to operations that
    // have not yet executed in baseline.
    if (graph_.osrBlock()) {
        MBasicBlock *osrBlock = graph_.osrBlock();
        JS_ASSERT(!osrBlock->isMarked());
        if (!enqueue(osrBlock, worklist))
            return false;
        for (size_t i = 0; i < osrBlock->numSuccessors(); i++) {
            if (!osrBlock->getSuccessor(i)->isMarked()) {
                // OSR block has an otherwise unreachable successor, abort.
                for (MBasicBlockIterator iter(graph_.begin()); iter != graph_.end(); iter++)
                    iter->mark();
                marked_ = graph_.numBlocks();
                return true;
            }
        }
    }

    // Now that we know we will not abort due to OSR, go back and
    // transform any tests on constant operands into gotos.
    for (uint32_t i = 0; i < optimizableBlocks.length(); i++) {
        MBasicBlock *block = optimizableBlocks[i];
        MBasicBlock *succ = optimizableSuccessor(block);
        JS_ASSERT(succ);

        MGoto *gotoIns = MGoto::New(succ);
        block->discardLastIns();
        block->end(gotoIns);
        MBasicBlock *successorWithPhis = block->successorWithPhis();
        if (successorWithPhis && successorWithPhis != succ)
            block->setSuccessorWithPhis(NULL, 0);
    }

    return true;
}

void
UnreachableCodeElimination::checkDependencyAndRemoveUsesFromUnmarkedBlocks(MDefinition *instr)
{
    // When the instruction depends on removed block,
    // alias analysis needs to get rerun to have the right dependency.
    if (instr->dependency() && !instr->dependency()->block()->isMarked())
        rerunAliasAnalysis_ = true;

    for (MUseIterator iter(instr->usesBegin()); iter != instr->usesEnd(); ) {
        if (!iter->consumer()->block()->isMarked()) {
            instr->setUseRemovedUnchecked();
            iter = instr->removeUse(iter);
        } else {
            iter++;
        }
    }
}

bool
UnreachableCodeElimination::removeUnmarkedBlocksAndClearDominators()
{
    // Removes blocks that are not marked from the graph.  For blocks
    // that *are* marked, clears the mark and adjusts the id to its
    // new value.  Also adds blocks that are immediately reachable
    // from an unmarked block to the frontier.

    size_t id = marked_;
    for (PostorderIterator iter(graph_.poBegin()); iter != graph_.poEnd();) {
        if (mir_->shouldCancel("Eliminate Unreachable Code"))
            return false;

        MBasicBlock *block = *iter;
        iter++;

        // Unconditionally clear the dominators.  It's somewhat complex to
        // adjust the values and relatively fast to just recompute.
        block->clearDominatorInfo();

        if (block->isMarked()) {
            block->setId(--id);
            for (MPhiIterator iter(block->phisBegin()); iter != block->phisEnd(); iter++)
                checkDependencyAndRemoveUsesFromUnmarkedBlocks(*iter);
            for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++)
                checkDependencyAndRemoveUsesFromUnmarkedBlocks(*iter);
        } else {
            if (block->numPredecessors() > 1) {
                // If this block had phis, then any reachable
                // predecessors need to have the successorWithPhis
                // flag cleared.
                for (size_t i = 0; i < block->numPredecessors(); i++)
                    block->getPredecessor(i)->setSuccessorWithPhis(NULL, 0);
            }

            if (block->isLoopBackedge()) {
                // NB. We have to update the loop header if we
                // eliminate the backedge. At first I thought this
                // check would be insufficient, because it would be
                // possible to have code like this:
                //
                //    while (true) {
                //       ...;
                //       if (1 == 1) break;
                //    }
                //
                // in which the backedge is removed as part of
                // rewriting the condition, but no actual blocks are
                // removed.  However, in all such cases, the backedge
                // would be a critical edge and hence the critical
                // edge block is being removed.
                block->loopHeaderOfBackedge()->clearLoopHeader();
            }

            for (size_t i = 0, c = block->numSuccessors(); i < c; i++) {
                MBasicBlock *succ = block->getSuccessor(i);
                if (succ->isMarked()) {
                    // succ is on the frontier of blocks to be removed:
                    succ->removePredecessor(block);

                    if (!redundantPhis_) {
                        for (MPhiIterator iter(succ->phisBegin()); iter != succ->phisEnd(); iter++) {
                            if (iter->operandIfRedundant()) {
                                redundantPhis_ = true;
                                break;
                            }
                        }
                    }
                }
            }

            // When we remove a call, we can't leave the corresponding MPassArg
            // in the graph. Since lowering will fail. Replace it with the
            // argument for the exceptional case when it is kept alive in a
            // ResumePoint. DCE will remove the unused MPassArg instruction.
            for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++) {
                if (iter->isCall()) {
                    MCall *call = iter->toCall();
                    for (size_t i = 0; i < call->numStackArgs(); i++) {
                        JS_ASSERT(call->getArg(i)->isPassArg());
                        JS_ASSERT(call->getArg(i)->defUseCount() == 1);
                        MPassArg *arg = call->getArg(i)->toPassArg();
                        arg->replaceAllUsesWith(arg->getArgument());
                    }
                }
            }

            graph_.removeBlock(block);
        }
    }

    JS_ASSERT(id == 0);

    return true;
}