/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

/**
 * @author Intel, Evgueni Brevnov
 *
 */

#include "irmanager.h"
#include "LoopTree.h"
#include "Dominator.h"
#include "ssa/SSA.h"

namespace Jitrino {

DEFINE_SESSION_ACTION(ThrowOptimizerPass, throwopt, "Throw Instruction Eliminator")

class ThrowInstEliminator {
public:
    ThrowInstEliminator(IRManager& irm);
    void eliminateThrowInst();
private:
    Node * findExceptionHandler(Type * exceptionType, Node * dispatch_node, StlVector<Inst *> & exit_markers);

    IRManager& irManager;
    ControlFlowGraph& flowGraph;
    InstFactory& instFactory;
    OpndManager& opndManager;
};

void ThrowOptimizerPass::_run(IRManager& irm) {
    ThrowInstEliminator throwopt(irm);
    throwopt.eliminateThrowInst();
}


ThrowInstEliminator::ThrowInstEliminator(IRManager& irm):
    irManager(irm), flowGraph(irm.getFlowGraph()),
    instFactory(irm.getInstFactory()), opndManager(irm.getOpndManager()) {}

void ThrowInstEliminator::eliminateThrowInst() {
    const Nodes& nodes = flowGraph.getNodes();
    StlVector<bool> visited_nodes(irManager.getMemoryManager(), flowGraph.getMaxNodeId(), false);
    StlVector<Inst *> pseudo_insts(irManager.getMemoryManager(), 10);
    StlVector<Edge *> exception_edges(irManager.getMemoryManager());
    LoopTree * loop_tree = irManager.getLoopTree();    
    bool restore_ssa = false;

    loop_tree->rebuild(false);

    for(Nodes::const_iterator node_iter = nodes.begin(), end = nodes.end(); node_iter != end; ++node_iter) {
        Node * throw_node = *node_iter;
        Inst * throw_inst = (Inst *)throw_node->getLastInst();
        
        if (throw_inst->getOpcode() != Op_Throw) continue;
        
        Opnd * throw_opnd = throw_inst->getSrc(0);
        Type * throw_type = throw_opnd->getType();
        
        pseudo_insts.clear();

        Node * dispatch_node = throw_node->getExceptionEdgeTarget();
        Node * catch_node = findExceptionHandler(throw_type, dispatch_node, pseudo_insts);

        if (catch_node) {
            assert(catch_node->isCatchBlock());
            
            // Find target block and catch instruction.
            Node * target_node = catch_node;
            Inst * catch_inst = NULL;
            do {
                for (Inst * i = (Inst *)target_node->getSecondInst(); i != NULL; i = i->getNextInst()) {
                    if (i->getOpcode() == Op_Catch) {
                        catch_inst = i;
                        break;
                    }
                }
            } while (catch_inst == NULL && (target_node = target_node->getUnconditionalEdgeTarget()) != NULL);

            assert(target_node);
            assert(catch_inst->getOpcode() == Op_Catch);

            if (Log::isEnabled()) {
                Log::out() << "Trying to elimination ";
                throw_inst->print(Log::out());
                Log::out() << std::endl;
            }


            // Avoid jumps inside loop.
            Node * throw_loop_header = loop_tree->getLoopHeader(throw_node, false);
            Node * target_loop_header = loop_tree->getLoopHeader(target_node, false);
            if (// Target node inside loop &&
                target_loop_header != NULL &&
                // Throw node is outside the same loop   ||  Target node is loop header
                (target_loop_header != throw_loop_header ||  target_node == target_loop_header)) {
                 
                if (Log::isEnabled()) {
                    Log::out() << "FAILED: Avoid jump inside loop from node ID " << throw_node->getId()
                        << " to node ID " << target_node->getId() << std::endl;
                }                    
                continue;
            }

            Opnd * catch_opnd = catch_inst->getDst();
            VarOpnd * dst_var = NULL;
            Inst * st_inst = NULL;
            // Detect true target node.
            if (visited_nodes[target_node->getId()]) {
                st_inst = (Inst *)target_node->getLastInst();
                dst_var = st_inst->getDst()->asVarOpnd();
                target_node = target_node->getUnconditionalEdgeTarget();
            } else {
                // Store exception operand in variable.
                Opnd * new_catch_opnd = opndManager.createSsaTmpOpnd(catch_opnd->getType());
                catch_inst->setDst(new_catch_opnd);
                dst_var = opndManager.createVarOpnd(catch_opnd->getType(), false);
                st_inst = instFactory.makeStVar(dst_var, new_catch_opnd);
                target_node->appendInst(st_inst, catch_inst);                
                // Mark the node as visited.
                visited_nodes[target_node->getId()] = true;
                // Split target node if required.
                if (target_node->getInstCount() > 2) {
                    target_node = flowGraph.splitNodeAtInstruction(st_inst, true, false, instFactory.makeLabel());
                } else {
                    target_node = target_node->getUnconditionalEdgeTarget();
                }
                target_node->prependInst(instFactory.makeLdVar(catch_opnd, dst_var));
            }

            // Replace "throw" wtih "stVar" instruction.
            throw_inst->unlink();
            throw_node->appendInst(instFactory.makeStVar(dst_var, throw_opnd));

            // Add direct jump.
            flowGraph.addEdge(throw_node, target_node);

            // Remember exception edge here to remove them all at once at the end.
            // Removing exception edge right now will generate unreachable code.
            exception_edges.push_back(throw_node->getExceptionEdge());

            // Add pseudo instructions from exeption path.            
            if (pseudo_insts.size() > 0) {
                Node * pseudo_node = flowGraph.spliceBlockOnEdge(
                    throw_node->getUnconditionalEdge(), instFactory.makeLabel());
                
                Inst * last_phi_inst = NULL;
                for(StlVector<Inst *>::iterator it = pseudo_insts.begin(); it != pseudo_insts.end(); it++) {
                    Inst * inst = *it;
                    Inst * new_inst = NULL;
                    if (inst->isMethodMarker()) {
                        MethodMarkerInst * marker_inst = (MethodMarkerInst *)inst;
                        new_inst = instFactory.makeMethodMarker(marker_inst->isMethodEntryMarker()
                            ? MethodMarkerInst::Entry : MethodMarkerInst::Exit, marker_inst->getMethodDesc());
                        pseudo_node->appendInst(new_inst);
                    } else if (inst->isPhi()) {
                        // Replace destination operand.
                        Opnd * orig_dst = inst->getDst();
                        VarOpnd * var = orig_dst->asSsaVarOpnd()->getVar();
                        Opnd * dst1 = opndManager.createSsaVarOpnd(var);
                        inst->setDst(dst1);
                        // Create phi instruction to stick source operands on new path.
                        U_32 num_opnds = inst->getNumSrcOperands();
                        Opnd** opnds = new (irManager.getMemoryManager()) Opnd*[num_opnds];
                        for (U_32 i = 0; i < num_opnds; ++i) {
                            opnds[i] = inst->getSrc(i);
                        }
                        Opnd * dst2 = opndManager.createSsaVarOpnd(var);
                        new_inst = instFactory.makePhi(dst2, num_opnds, opnds);
                        // Phi is a header critical instruction thus it must go in the beginning.
                        if (last_phi_inst == NULL) {
                            pseudo_node->prependInst(new_inst);
                        } else {
                            pseudo_node->appendInst(new_inst, last_phi_inst);
                        }
                        last_phi_inst = new_inst;
                        // Create one more phi to stick destination operands.
                        Opnd * dst_opnds[] = {dst1, dst2};
                        new_inst = instFactory.makePhi(orig_dst, 2, dst_opnds);
                        target_node->prependInst(new_inst);
                    } else {
                        assert("Unexcpected type of instruction in dispatch node.");
                    }
                }
            }

            // Rebuild loop tree after modifications.
            loop_tree->rebuild(false);
            restore_ssa = true;

            if (Log::isEnabled()) {
                Log::out() << "SUCCEED: Inserting direct jump from node ID " << throw_node->getId()
                    << " to node ID " << target_node->getId() << std::endl;
            }                    
        }
    }

    if (restore_ssa) {
        // Remove all remembered exception edges.
        for (StlVector<Edge *>::iterator it = exception_edges.begin(); it != exception_edges.end(); it++) {
            flowGraph.removeEdge(*it);
        }

        // Clean up dead code.
        OptPass::dce(irManager);
        OptPass::uce(irManager, false);

        // Restrore SSA form.
        OptPass::computeDominators(irManager);
        DominatorTree* dominatorTree = irManager.getDominatorTree();
        
        DomFrontier frontier(irManager.getNestedMemoryManager(), *dominatorTree, &flowGraph);
        SSABuilder ssaBuilder(opndManager, instFactory, frontier, &flowGraph, irManager.getOptimizerFlags());
        bool phiInserted = ssaBuilder.fixupVars(&flowGraph, irManager.getMethodDesc());
        irManager.setInSsa(true);
        if (phiInserted) {
            irManager.setSsaUpdated();
        }
    }
}

Node * ThrowInstEliminator::findExceptionHandler(Type * exceptionType, Node * dispatch_node, StlVector<Inst *> & pseudo_insts) {
    const Edges & catch_eges = dispatch_node->getOutEdges();
    Edges::const_iterator edge_iter;

    assert(dispatch_node != NULL);

    // Scan dispatch node for possible method end markers.
    Inst * inst = (Inst *)dispatch_node->getSecondInst();
    while (inst != NULL) {
        pseudo_insts.push_back(inst);
        inst = inst->getNextInst();
    }

    for(edge_iter = catch_eges.begin(); edge_iter != catch_eges.end(); ++edge_iter) {
        Edge * catch_edge = *edge_iter;
        Node * catch_node = catch_edge->getTargetNode();
        
        if (!catch_node->isBlockNode()) continue;
        
        CatchLabelInst * catch_label_inst =
            ((Inst *)catch_node->getFirstInst())->asCatchLabelInst();
        Type * catch_type = catch_label_inst->getExceptionType();
        if (irManager.getTypeManager().isSubTypeOf(exceptionType, catch_type)) {
            return catch_node;
        }
    }

    // Exception handler was not found.
    // Go to next dispatch node.
    dispatch_node = dispatch_node->getExceptionEdgeTarget();

    if (dispatch_node && dispatch_node->isDispatchNode()) {
        return findExceptionHandler(exceptionType, dispatch_node, pseudo_insts);
    }

    return NULL;
}

} //namespace Jitrino