/*
 *  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, Pavel A. Ozhdikhin
 *
 */

#include "deadcodeeliminator.h"
#include "irmanager.h"
#include "Inst.h"
#include "Stl.h"
#include "BitSet.h"
#include "MemoryManager.h"
#include "Log.h"
#include "constantfolder.h"
#include "optimizer.h"
#include "XTimer.h"
#include "PMFAction.h"
#include "Dominator.h"
#include "FlowGraph.h"

namespace Jitrino {

// Timer.h includes windows.h, which has a broken #def of min:
#undef min

DEFINE_SESSION_ACTION(DeadCodeEliminationPass, dce, "Dead Code Elimination")

void
DeadCodeEliminationPass::_run(IRManager& irm){
    DeadCodeEliminator dce(irm);
    {
        //create loops mapping to be able to fix infinite loops after the optimization
        MemoryManager tmpMM("HashValueNumberingPass::_run");
        InfiniteLoopsInfo loopsMapping(tmpMM);
        DeadCodeEliminator::createLoop2DispatchMapping(irm.getFlowGraph(), loopsMapping);

        //perform optimization
        dce.eliminateDeadCode(false);

        //fix infinite loops if found
        DeadCodeEliminator::fixInfiniteLoops(irm, loopsMapping);
    }
}

DEFINE_SESSION_ACTION(UnreachableCodeEliminationPass, uce, "Unreachable Code Elimination");

void 
UnreachableCodeEliminationPass::_run(IRManager& irm) {
    DeadCodeEliminator dce(irm);
    {
        dce.eliminateUnreachableCode();
    }
    bool fixup_ssa = irm.getOptimizerFlags().fixup_ssa;
    if (irm.getInSsa() && fixup_ssa) {
        OptPass::fixupSsa(irm);
    }
}

DEFINE_SESSION_ACTION(ExtraPseudoThrowRemovalPass, rept, "Removal of Extra PseudoThrow Instructions");

void 
ExtraPseudoThrowRemovalPass::_run(IRManager& irm) {
    DeadCodeEliminator dce(irm);
    dce.removeExtraPseudoThrow();
}


//Empty Node Removal
class PurgeEmptyNodesPass: public SessionAction {
public:
    void run();    
};
ActionFactory<PurgeEmptyNodesPass> _purge("purge");

void
PurgeEmptyNodesPass::run() {
    IRManager& irm = *getCompilationContext()->getHIRManager();
    irm.getFlowGraph().purgeEmptyNodes(false);
}

//
// Returns true if an instruction is a non-essential instruction
// Essential instructions are exception throwing instructions, calls,
// returns, stores, and branches.  Once we have control dependence 
// information branches are non-essential.
//
static bool
isNonEssential(Inst* inst) {
    Operation operation = inst->getOperation();
    if (operation.isNonEssential()) {
        return true;
    } else {
        Opcode opCode = inst->getOpcode();
        if (opCode == Op_StVar) {
            // StVar is non-essential if the variable to which it stores is in SSA form
            return inst->getDst()->isSsaVarOpnd();
        } else if (opCode == Op_NewObj) {
            Type* dstType = inst->getDst()->getType();
            assert(!dstType->isUnresolvedObject());
            // Objects that have finalizers must not be swept
            return !dstType->asNamedType()->isFinalizable();
        }
        return false;
    }
}

static U_8
getBitWidth(Type::Tag tag)
{
    switch (tag) {
    case Type::Void: return 0;
    case Type::Boolean: return 1;
    case Type::Char: return 16;
    case Type::Int8: return 8;
    case Type::Int16: return 16;
    case Type::Int32: return 32;
    case Type::Int64: return 64;
    case Type::UInt8: return 8;
    case Type::UInt16: return 16;
    case Type::UInt32: return 32;
    case Type::UInt64: return 64;

    default: return 0xff; // uses all;
    }        
}

// returns the number of bits of the given opnd_num which is used,
// given that dst_bits of the dst are used
static U_8
usesBitsOfOpnd(U_8 dst_bits, Inst* inst, U_32 opnd_num) {
    U_8 opwidth = getBitWidth(inst->getType());
    Opnd *opnd = inst->getSrc(opnd_num);
    U_8 opndwidth = getBitWidth(opnd->getType()->tag);
    U_8 res = opndwidth;
    switch (inst->getOpcode()) {
    case Op_Add:   case Op_Mul:    case Op_Sub:
        res = ::std::min(dst_bits, opwidth); break;
    case Op_TauDiv:   case Op_TauRem:    
        res = dst_bits; break;
    case Op_Neg:   
        res = ::std::min(dst_bits, opwidth); break;
    case Op_MulHi:
        res = opwidth; break;
    case Op_Min:   case Op_Max:   case Op_Abs:
    case Op_And:   case Op_Or:    case Op_Xor:    case Op_Not:
        res = ::std::min(dst_bits, opwidth); break;
    case Op_Select:
        if (opnd_num == 0) res = opndwidth;
        else res = dst_bits;
        break;
    case Op_Conv:
        res = ::std::min(dst_bits, opwidth); break;
    case Op_Shladd:  
        {
            switch (opnd_num) {
            case 0:
                {
                    Opnd *shiftAmount = inst->getSrc(1);
                    I_32 shiftby;
                    bool isconst = 
                        ConstantFolder::isConstant(shiftAmount->getInst(), 
                                                   shiftby);
                    if( !(isconst && (shiftby > 0)) ) assert(0);
                    res = ::std::min(dst_bits, opwidth)-(U_8)shiftby;
                    break;
                }
            case 1:
                {
                    res = opndwidth;
                    break;
                }
            case 2:
                {
                    res = ::std::min(dst_bits, opwidth);
                    break;
                }
            default:
                assert(0);
            }
            break;
        }        
    case Op_Shl:
        {
            switch (opnd_num) {
            case 0:
                {
                    Opnd *shiftAmount = inst->getSrc(1);
                    I_32 shiftby;
                    bool isconst 
                        = ConstantFolder::isConstant(shiftAmount->getInst(), 
                                                     shiftby);
                    if (isconst && shiftby > 0) {
                        res = ::std::min(dst_bits, opwidth)-(U_8)shiftby;
                        break;
                    }
                }
            case 1:
                {
                    res = opndwidth;
                }
                break;
            default:
                assert(0);
            };
            break;
        }
    case Op_Shr:   
        res = opndwidth; break;
    case Op_Cmp:    case Op_Cmp3:
    case Op_Copy:
        res = ::std::min(dst_bits, opwidth); break;
    case Op_LdVar:
        res = dst_bits; break;
    case Op_Phi:
        res = dst_bits; break;
    case Op_StVar: 
        if (inst->getDst()->isSsaVarOpnd()) {
            res = dst_bits;
        } else {
            res = opndwidth; // can't track value accurately, be conservative
        }
        break;
    case Op_TauStElem:
    case Op_TauStRef: 
        {
            if (opnd_num == 0) { // value to be stored, trim to opwidth
                res = opwidth;
            }
        }
        break;
    case Op_TauStInd:
    case Op_TauStField: 
        {
            if (opnd_num == 0) { // value to be stored, trim to opwidth
                res = opwidth;
            }
        }
        break;
    case Op_TauStStatic:
        {
            if (opnd_num == 0) { // value to be stored, trim to opwidth
                res = opwidth;
            }
        }
        break;
    default:
        {
            res = opndwidth;
        }
    }
    U_8 res1 = ::std::min(res, opndwidth);
    return res1;
}

DeadCodeEliminator::DeadCodeEliminator(IRManager& irm) 
: irManager(irm), flowGraph(irm.getFlowGraph()), returnOpnd(irm.getReturnOpnd()) 
{
    preserveCriticalEdges = irManager.getOptimizerFlags().preserve_critical_edges;
}

Opnd*
DeadCodeEliminator::findDefiningTemp(Opnd* var) {
    SsaVarOpnd* ssaVarOpnd = var->asSsaVarOpnd();
    if(ssaVarOpnd == NULL) {
        Log::out() << "Nothing found: Not SSA" << ::std::endl;
        return NULL; // not an SsaVarOpnd
    }
    Inst* inst = ssaVarOpnd->getInst();
    assert(inst->getNode());
    if(inst->getOpcode() == Op_StVar) {
        // propagate src of copy recursively
        copyPropagate(inst);
        if(Log::isEnabled()) {
            Log::out() << "Found: ";
            Inst* def = inst->getSrc(0)->getInst();
            if(def != NULL) {
                def->print(Log::out());
            }
            else { 
                Log::out() << "Dangling operand "; inst->getSrc(0)->print(Log::out()); 
            }
            Log::out() << ::std::endl;
        }
        return inst->getSrc(0);
    } else if(inst->getOpcode() == Op_Phi) {

        Opnd* tmp = NULL;
        U_32 n = inst->getNumSrcOperands();
        for(U_32 j=0; j < n; ++j) {
            Opnd* src = inst->getSrc(j);
            Inst* srcInst = src->getInst();
            assert(srcInst->getNode());
            if(srcInst == NULL || srcInst->getOpcode() != Op_StVar) {
                tmp = NULL;
                break;
            }
            assert(srcInst->getOpcode() == Op_StVar);
            if(tmp == NULL) {
                assert(j == 0);
                tmp = srcInst->getSrc(0);
            } else if(tmp != srcInst->getSrc(0)) {
                tmp = NULL;
                break;
            }
        }

        return tmp;
    }
    Log::out() << "Nothing found: Not stVar or phi instruction" << ::std::endl;
    return NULL;
}


Opnd*
DeadCodeEliminator::copyPropagate(Opnd* opnd) {
    SsaOpnd* src = opnd->asSsaOpnd();
    if (src == NULL)
        return opnd;   // src was not a SsaOpnd so it cannot be propagated
    Inst* srcInst = src->getInst();
    assert(srcInst->getNode());
    if (srcInst == NULL)
        return opnd;
    if (srcInst->getOpcode() == Op_Copy) {
        // propagate src of copy recursively
        copyPropagate(srcInst);
        return srcInst->getSrc(0);
    } else if (srcInst->getOpcode() == Op_LdVar) {
        // propagate src of LdVar if src SsaVarOpnd comes from a StVar
        Opnd* tmp = findDefiningTemp(srcInst->getSrc(0));
        if(tmp != NULL) {
            return tmp;
        } else {
            return opnd;
        }
    } else if (srcInst->getOpcode() == Op_Phi) {
        // propagate src of degenerate phi (phi with only one arg).
        if(srcInst->getNumSrcOperands() != 1)
            return opnd;
        // propagate src of copy recursively
        copyPropagate(srcInst);
        // reset inst's source to propagates src
        return srcInst->getSrc(0);
    }
    return opnd;
}

void
DeadCodeEliminator::copyPropagate(Inst* inst) {
    U_32 numSrcs = inst->getNumSrcOperands();
    for (U_32 i=0; i<numSrcs; i++) {
        Opnd* opnd = inst->getSrc(i);
        Opnd* propagated = copyPropagate(opnd);
        if (opnd != propagated) {
            if (Log::isEnabled()) {
                Log::out() << "    Operand "; opnd->print(Log::out());
                Log::out() << " replaced by "; propagated->print(Log::out());
                Log::out() << std::endl;
            }
            inst->setSrc(i, propagated);
        }
    }
}

//
// marks an instruction as live and add its sources to the work set
//
static void
markLiveInst1(Inst* inst,
              InstDeque& workSet,
              BitSet& usefulInstSet,
              BitSet& usefulVarSet,
              U_32 minInstId,
              U_32 maxInstId) {
    //
    // add instruction's sources to the work list
    //
    assert(inst);
    assert(inst->getNode());

    U_8 dstWidth = 255;

    if (Log::isEnabled()) {
        Log::out() << "Found dstwidth of " << (int) dstWidth
                   << " for inst ";
        inst->print(Log::out());
        Log::out() << ::std::endl;
    }

    for (U_32 i=0; i<inst->getNumSrcOperands(); i++) {
        Opnd* src = inst->getSrc(i);
        // only follow ssa use-def links
        SsaOpnd* srcSsaOpnd = src->asSsaOpnd();
        if (srcSsaOpnd != NULL) {
            // use of an ssa operand
            Inst* def = srcSsaOpnd->getInst();
            if(def == NULL)
                continue;
            assert(def != NULL);

            assert(def->getNode());
            U_8 opndWidth = 255;
            U_32 defId = def->getId();

            if (usefulInstSet.setBit(defId-minInstId, true)) {
                // was already marked as live, check old width.
                U_8 oldOpndWidth = 255;

                if (Log::isEnabled()) {
                    Log::out() << "Found dstwidth of " << (int) oldOpndWidth
                               << " for inst ";
                    def->print(Log::out());
                    Log::out() << ::std::endl;
                }

                if (opndWidth > oldOpndWidth) {
                    if (Log::isEnabled()) {
                        Log::out() << "Setting dstwidth to " << (int) opndWidth
                                   << " for inst ";
                        def->print(Log::out());
                        Log::out() << ::std::endl;
                    }
                    workSet.pushFront(def);                    
                }
            } else {
                if (Log::isEnabled()) {
                    Log::out() << "Setting dstwidth to " << (int) opndWidth
                               << " for inst ";
                    def->print(Log::out());
                    Log::out() << ::std::endl;
                }
                workSet.pushFront(def);
            }
            // mark ssavaropnds as not dead
            SsaVarOpnd* ssaVarOpnd = src->asSsaVarOpnd();
            if (ssaVarOpnd != NULL) {
                // mark var as useful
                usefulVarSet.setBit(ssaVarOpnd->getVar()->getId(),true);
            }
        } else {
            VarOpnd* srcVarOpnd = src->asVarOpnd();
            if (srcVarOpnd != NULL) {
                // use of a var opnd (ldvar or ldvara)
                // mark var as useful
                usefulVarSet.setBit(srcVarOpnd->getId(),true);
            }
        }
    }
}

//
// Deletes instructions that are not marked as useful
//
void
DeadCodeEliminator::sweepInst1(Node* node, 
                               Inst* inst,
                               BitSet& usefulInstSet,
                               BitSet& usefulVarSet,
                               U_32 minInstId,
                               U_32 maxInstId,
                               bool canRemoveStvars) {
    assert(inst);
    assert(inst->getNode());
    U_32 instId = inst->getId();
    if (inst->isMethodMarker()) {
        // don't remove a method marker, but remove opcode if it is dead
        if (inst->getNumSrcOperands() > 0) {
            Opnd *opnd = inst->getSrc(0);
            if (opnd && !opnd->isNull()) {
                Inst *srcInst = opnd->getInst();
                assert(srcInst);
                assert(srcInst->getNode());
                U_32 srcId = srcInst->getId();
                // instructions are only added during analysis for
                // live instructions, so if it's not in the map, 
                // assume it is live
                if ((minInstId <= srcId) &&
                    (srcId < maxInstId) &&
                    (usefulInstSet.getBit(srcId-minInstId) == false)) {
                    MethodMarkerInst *mmi = inst->asMethodMarkerInst();
                    // Method marker could contain retOpnd
                    if (!mmi->getMethodDesc()->isStatic()) {
                    mmi->removeOpnd();
                }
            }
        }            
        }            
    } else if ((minInstId <= instId) && (instId < maxInstId) &&
               usefulInstSet.getBit(instId-minInstId) == false) {
        // inst is a useless instruction
        if (Log::isEnabled()) {
            Log::out() << "Useless inst found, removing: ";
            inst->print(Log::out());
            Log::out() << ::std::endl;
            Log::out() << " instId=" << (int)instId;
            Log::out() << ", minInstId=" << (int)minInstId;
            Log::out() << ", maxInstId=" << (int)maxInstId;
            Log::out() << ::std::endl;
        }
        inst->unlink();
        if (inst->isBranch()) {
            assert(0);
        } else if (inst->isSwitch()) {
            assert(0);
        } else if (inst->getOperation().canThrow()) {
            flowGraph.removeEdge(node->getExceptionEdge());
        }
        return;
    }
    //
    // delete stores to useless variables
    //
    if (canRemoveStvars && inst->getOpcode() == Op_StVar) {
        VarOpnd* dstVarOpnd = inst->getDst()->asVarOpnd();
        if (dstVarOpnd == NULL)
            return;
        if (usefulVarSet.getBit(dstVarOpnd->getId()) == false) {
            //
            // store to a useless variable
            //
            if (Log::isEnabled()) {
                Log::out() << "Removing store to useless var: ";
                inst->print(Log::out());
                Log::out() << ::std::endl;
            }
            inst->unlink();
            return;
        }       
    }
}

//
// marks an instruction as live and add its sources to the work set
//
static void
markLiveInst(Inst* inst,
             InstDeque& workSet,
             BitSet& usefulInstSet,
             BitSet& usefulVarSet,
             U_8 *usedInstWidth,
             U_32 minInstId,
             U_32 maxInstId) {
    //
    // add instruction's sources to the work list
    //
    assert(inst);
    assert(inst->getNode());
    U_32 instId = inst->getId();
    assert(usedInstWidth);
    assert((instId >= minInstId) && (instId < maxInstId));
    U_8 dstWidth = usedInstWidth[instId-minInstId];

    if (Log::isEnabled()) {
        Log::out() << "Found dstwidth of " << (int) dstWidth
                   << " for inst ";
        inst->print(Log::out());
        Log::out() << ::std::endl;
    }

    for (U_32 i=0; i<inst->getNumSrcOperands(); i++) {
        Opnd* src = inst->getSrc(i);
        // only follow ssa use-def links
        SsaOpnd* srcSsaOpnd = src->asSsaOpnd();
        if (srcSsaOpnd != NULL) {
            // use of an ssa operand
            Inst* def = srcSsaOpnd->getInst();
            if(def == NULL)
                continue;
            assert(def != NULL);

            U_8 opndWidth = usesBitsOfOpnd(dstWidth, inst, i);
            assert(def);
            assert(def->getNode());
            U_32 defId = def->getId();

            if (!((minInstId <= defId) && (defId < maxInstId))) {
                // this instruction is out of the region, skip it.
                
                if (Log::isEnabled()) {
                    Log::out() << "Skipping outside-region inst ";
                    def->print(Log::out());
                    Log::out() << ::std::endl;
                }
            } else if (usefulInstSet.setBit(defId-minInstId, true)) {
                // was already marked as live, check old width.
                U_8 oldOpndWidth = usedInstWidth[defId-minInstId];

                if (Log::isEnabled()) {
                    Log::out() << "Found dstwidth of " << (int) oldOpndWidth
                               << " for inst ";
                    def->print(Log::out());
                    Log::out() << ::std::endl;
                }

                if (opndWidth > oldOpndWidth) {
                    if (Log::isEnabled()) {
                        Log::out() << "Setting dstwidth to " << (int) opndWidth
                                   << " for inst ";
                        def->print(Log::out());
                        Log::out() << ::std::endl;
                    }
                    usedInstWidth[defId-minInstId] = opndWidth;
                    workSet.pushFront(def);                    
                }
            } else {
                if (Log::isEnabled()) {
                    Log::out() << "Setting dstwidth to " << (int) opndWidth
                               << " for inst ";
                    def->print(Log::out());
                    Log::out() << ::std::endl;
                }
                usedInstWidth[defId-minInstId] = opndWidth;
                workSet.pushFront(def);
            }
            // mark ssavaropnds as not dead
            SsaVarOpnd* ssaVarOpnd = src->asSsaVarOpnd();
            if (ssaVarOpnd != NULL) {
                // mark var as useful
                usefulVarSet.setBit(ssaVarOpnd->getVar()->getId(),true);
            }
        } else {
            VarOpnd* srcVarOpnd = src->asVarOpnd();
            if (srcVarOpnd != NULL) {
                // use of a var opnd (ldvar or ldvara)
                // mark var as useful
                usefulVarSet.setBit(srcVarOpnd->getId(),true);
            }
        }
    }
}

//
// Deletes instructions that are not marked as useful
//
void
DeadCodeEliminator::sweepInst(Node* node, 
                              Inst* inst,
                              BitSet& usefulInstSet,
                              BitSet& usefulVarSet,
                              U_8 *usedInstWidth,
                              U_32 minInstId,
                              U_32 maxInstId,
                              bool canRemoveStvars) {
    assert(usedInstWidth);
    assert(inst);
    assert(inst->getNode());
    U_32 instId = inst->getId();
    if (inst->isMethodMarker()) {
        // don't remove a method marker, but remove opcode if it is dead
        if (inst->getNumSrcOperands() > 0) {
            Opnd *opnd = inst->getSrc(0);
            if (opnd && !opnd->isNull()) {
                Inst *srcInst = opnd->getInst();
                assert(srcInst);
                assert(srcInst->getNode());
                U_32 srcId = srcInst->getId();
                // instructions are only added during analysis for
                // live instructions, so if it's not in the map, 
                // assume it is live
                if ((minInstId <= srcId) && (srcId < maxInstId) &&
                    (usefulInstSet.getBit(srcId-minInstId) == false)) {
                    MethodMarkerInst *mmi = inst->asMethodMarkerInst();
                    // Method marker could contain retOpnd which should be preserved
                    if (!mmi->getMethodDesc()->isStatic()) {
                    mmi->removeOpnd();
                }
            }
        }            
        }            
    } else if ((minInstId <= instId) && (instId < maxInstId) &&
               usefulInstSet.getBit(instId-minInstId) == false) {
        // inst is a useless instruction
        if (Log::isEnabled()) {
            Log::out() << "Useless inst found, removing: ";
            inst->print(Log::out());
            Log::out() << ::std::endl;
            Log::out() << " instId=" << (int)instId;
            Log::out() << ", minInstId=" << (int)minInstId;
            Log::out() << ", maxInstId=" << (int)maxInstId;
            Log::out() << ::std::endl;
        }
        inst->unlink();
        if (inst->isBranch()) {
            assert(0);
        } else if (inst->isSwitch()) {
            assert(0);
        } else if (inst->getOperation().canThrow()) {
            flowGraph.removeEdge(node->getExceptionEdge());
        }
        return;
    } else {
        switch (inst->getOpcode()) {
        case Op_Conv:
            {
                Type::Tag instType = inst->getType();
                
                if ((!Type::isInteger(instType)) ||
                    ((inst->getOverflowModifier() != Overflow_None) &&
                     (inst->getExceptionModifier() != Exception_Never))) 
                    break;

                Type *srcType = inst->getSrc(0)->getType();
                if (!srcType->isInteger())
                    break;
        
                U_8 convSize = getBitWidth(instType);
                U_8 srcSize = getBitWidth(srcType->tag);
                U_8 dstSize = getBitWidth(inst->getDst()->getType()->tag);

                if (dstSize != srcSize) {
                    // it's not just a sign-extension, we can't remove it
                    break;
                }

                assert((minInstId <= instId) && (instId < maxInstId));
                U_8 usedDstSize = usedInstWidth[instId-minInstId];

                if (Log::isEnabled()) {
                    Log::out() << "Found dstwidth of " << (int) usedDstSize
                               << " for inst ";
                    inst->print(Log::out());
                    Log::out() << ::std::endl;
                }
                
                if ((srcSize >= convSize) &&
                    (usedDstSize <= convSize)) {
                    // convert to a copy.
                    if (Log::isEnabled()) {
                        Log::out() << "Eliminating redundant conv ";
                        inst->print(Log::out());
                        Log::out() << ::std::endl;
                    }
                    InstFactory &factory = irManager.getInstFactory();
                    Inst *copyInst = factory.makeCopy(inst->getDst(), inst->getSrc(0));
                    copyInst->insertAfter(inst);
                    inst->unlink();
                    // copyInst doesn't appear in bitmaps, but we won't walk
                    // over it, so it is only tested for a MethodMarker Inst 
                    // operand above, and we are careful there
                }
            }
            break;
        default:
            break;
        }
    }
    //
    // delete stores to useless variables
    //
    if (canRemoveStvars && inst->getOpcode() == Op_StVar) {
        VarOpnd* dstVarOpnd = inst->getDst()->asVarOpnd();
        if (dstVarOpnd == NULL)
            return;
        if (usefulVarSet.getBit(dstVarOpnd->getId()) == false) {
            //
            // store to a useless variable
            //
            if (Log::isEnabled()) {
                Log::out() << "Removing store to useless var: ";
                inst->print(Log::out());
                Log::out() << ::std::endl;
            }
            inst->unlink();
            return;
        }       
    }
}

//
// Eliminate unreachable code
//
bool
DeadCodeEliminator::eliminateUnreachableCode() {
    MemoryManager memManager("DeadCodeEliminator::eliminateUnreachableCode");

    // Purge unreachable nodes from CFG.
    Nodes unreachableNodes(memManager);
    irManager.getFlowGraph().purgeUnreachableNodes(unreachableNodes);   

    // If no unreachable nodes, return
    if(unreachableNodes.empty())
        return false;

    // Clear the set of unreachable definitions.
    StlHashSet<U_32> unreachableDefSet(memManager);

    StlVector<Node*>::iterator niter;
    for(niter = unreachableNodes.begin(); niter != unreachableNodes.end(); ++niter) {
        Node* node = *niter;

        // Find unreachable defs.  Note, only SsaVarOpnds can be used 
        // in later reachable nodes.
        Inst* headInst = (Inst*)node->getFirstInst();
        assert(headInst->getNode());
        for (Inst* inst = headInst->getNextInst();inst!=NULL;inst=inst->getNextInst()) {
            assert(inst->getNode());
            SsaVarOpnd* dst = inst->getDst()->asSsaVarOpnd();
            if(dst != NULL) {
                assert(inst->getOpcode() == Op_StVar || inst->getOpcode() == Op_Phi);
                unreachableDefSet.insert(dst->getId());
            }
        }
    }

    // If no unreachable defs to cleanup, just return.
    if(unreachableDefSet.empty())
        return true;


    // Cleanup up phi instructions.
    const Nodes& nodes = flowGraph.getNodes();
    Nodes::const_iterator niter2;
    for(niter2 = nodes.begin(); niter2 != nodes.end(); ++niter2) {
        Node* node = *niter2;
        Inst* headInst = (Inst*)node->getFirstInst();
        assert(headInst->getNode());
        for (Inst* inst = headInst->getNextInst();inst!=NULL;inst=inst->getNextInst()) {
            assert(inst->getNode());
            if(inst->getOpcode() == Op_Phi) {
#ifndef NDEBUG
                SsaVarOpnd* dst = inst->getDst()->asSsaVarOpnd();
                assert(dst!=NULL);
#endif
                U_32 numSrc = inst->getNumSrcOperands();
                U_32 numKill = 0;
                for(U_32 i = 0; i < numSrc; ++i) {
                    SsaVarOpnd* src = inst->getSrc(i)->asSsaVarOpnd();
                    assert(src != NULL);
                    if(unreachableDefSet.find(src->getId()) != unreachableDefSet.end()) {
                        // Purge this operand.
                        ++numKill;
                    } else {
                        // Shift down over purged operands.
                        assert(numKill <= i);
                        if(numKill > 0)
                            inst->setSrc(i-numKill, src);
                    }
                }
                if(numKill > 0)
                    ((PhiInst*) inst)->setNumSrcs(numSrc-numKill);
            }
        }
    }
    return true;
}

static CountTime dcePhase1Timer("opt::dce::phase1");
static CountTime dcePhase2Timer("opt::dce::phase2");
static CountTime dcePhase3Timer("opt::dce::phase3");
static CountTime dcePhase4Timer("opt::dce::phase4");
static CountTime dcePhase5Timer("opt::dce::phase5");
static CountTime dcePhase6Timer("opt::dce::phase6");

//
// Performs dead code elimination
//
void
DeadCodeEliminator::eliminateDeadCode(bool keepEmptyNodes) {
    // user should call eliminateUnreachableCode() first

    U_32 minInstId = irManager.getMinimumInstId();
    U_32 maxInstId = irManager.getInstFactory().getNumInsts();
    U_32 numInsts = maxInstId - minInstId;
    U_32 numOpnds = irManager.getOpndManager().getNumVarOpnds();
    MemoryManager memManager("DeadCodeEliminator::eliminateDeadCode");
    InstDeque workSet(memManager);
    Nodes nodes(memManager);
    flowGraph.getNodesPostOrder(nodes);
    Nodes::reverse_iterator niter;

    // set of useful instructions & variables; initially everything is useless
    BitSet usefulInstSet(memManager,numInsts+1);
    BitSet usefulVarSet(memManager,numOpnds+1);
    const OptimizerFlags& optimizerFlags = irManager.getOptimizerFlags();
    U_8 *usedInstWidth = optimizerFlags.dce2 ? new (memManager) U_8[numInsts] : 0;

    {
        AutoTimer t(dcePhase1Timer); 
        
    //
    // first propagate copies and initialize the work list with 
    // essential instructions
    //
    if (usedInstWidth) {
        for (niter = nodes.rbegin(); niter != nodes.rend(); ++niter) {
            Node* node = *niter;
            Inst* headInst = (Inst*)node->getFirstInst();
            assert(headInst->getNode());
            for (Inst* inst = headInst->getNextInst();inst!=NULL;inst=inst->getNextInst()) {
                assert(inst->getNode());
                // copy propagate all sources of this instruction
                copyPropagate(inst);
                // For inlined methods, the last instruction of the epilog copies the return value out.
                if (isNonEssential(inst) == false || (returnOpnd != NULL && returnOpnd == inst->getDst())) {
                    // add essential instruction to work list
                    assert(inst != NULL);
                    workSet.pushBack(inst);

                    assert(inst);
                    assert(inst->getNode());
                    U_32 instId = inst->getId();
                    usefulInstSet.setBit(instId-minInstId, true);
                    if (usedInstWidth) {
                        U_8 usedWidth = getBitWidth(inst->getType());
                        if (Log::isEnabled()) {
                            Log::out() << "Setting dstwidth to " << (int) usedWidth
                                       << " for inst ";
                            inst->print(Log::out());
                            Log::out() << ::std::endl;
                        }
                        assert((minInstId <= instId) && (instId < maxInstId));
                        usedInstWidth[instId-minInstId]= usedWidth;
                    }
                }
            }
        }
    } else {
        for (niter = nodes.rbegin(); niter != nodes.rend(); ++niter) {
            Node* node = *niter;
            Inst* headInst = (Inst*)node->getFirstInst();
            assert(headInst->getNode());
            for (Inst* inst = headInst->getNextInst();inst!=NULL;inst=inst->getNextInst()) {
                assert(inst->getNode());
                // copy propagate all sources of this instruction
                copyPropagate(inst);
                // For inlined methods, the last instruction of the epilog copies the return value out.
                if (isNonEssential(inst) == false || (returnOpnd != NULL && returnOpnd == inst->getDst())) {
                    // add essential instruction to work list
                    assert(inst != NULL);
                    workSet.pushBack(inst);

                    assert(inst);
                    assert(inst->getNode());
                    U_32 instId = inst->getId();
                    usefulInstSet.setBit(instId-minInstId, true);
                }
            }
        }
    }
    }

    {
        AutoTimer t(dcePhase2Timer); 

    //
    // Iteratively mark all useful instructions by computing slices
    //
    if (usedInstWidth) {
        while (!workSet.isEmpty()) {
            markLiveInst(workSet.popFront(),workSet,usefulInstSet,usefulVarSet,
                         usedInstWidth, minInstId, maxInstId);
        }
    } else {
        while (!workSet.isEmpty()) {
            markLiveInst1(workSet.popFront(),workSet,
                          usefulInstSet, usefulVarSet, minInstId, maxInstId);
        }
    }
    }

    {
        const bool canRemoveStVars = (irManager.getParent() == NULL); // we can remove a useless var
        AutoTimer t(dcePhase3Timer); 
        //
        // Now cleanup all the dead code
        //
        if (usedInstWidth) {
            for (niter = nodes.rbegin(); niter != nodes.rend(); ++niter) {
                Node* node = *niter;
                Inst* headInst = (Inst*)node->getFirstInst();
                assert(headInst->getNode());
                for (Inst* inst = headInst->getNextInst(); inst != NULL; ) {
                    assert(inst->getNode());
                    Inst *nextInst = inst->getNextInst();
                    sweepInst(node, inst,usefulInstSet,usefulVarSet,usedInstWidth,minInstId,maxInstId,canRemoveStVars);
                    inst = nextInst;
                }
            }
        } else {
            for (niter = nodes.rbegin(); niter != nodes.rend(); ++niter) {
                Node* node = *niter;
                Inst* headInst = (Inst*)node->getFirstInst();
                assert(headInst->getNode());
                for (Inst* inst = headInst->getNextInst(); inst != NULL; ) {
                    assert(inst->getNode());
                    Inst *nextInst = inst->getNextInst();
                    sweepInst1(node, inst,usefulInstSet,usefulVarSet,minInstId,maxInstId,canRemoveStVars);
                    inst = nextInst;
                }
            }
        }
    }

    {
        const bool canUnlink = (irManager.getParent() == NULL); // we can unlink an unused var

        AutoTimer t(dcePhase4Timer); 
        //
        // delete dead variables
        //
        OpndManager &opndManager = irManager.getOpndManager();
        VarOpnd *varOpnd0 = opndManager.getVarOpnds();
        if (varOpnd0) {
            VarOpnd *varOpnd = varOpnd0;
            // first check whether head needs to be deleted
            while (varOpnd == varOpnd0) {
                VarOpnd *nextVar = varOpnd->getNextVarOpnd();
                if (nextVar == varOpnd) nextVar = 0; // this should make us stop
                if (usefulVarSet.getBit(varOpnd->getId()) == true){
                    // live variable
                    varOpnd->setDeadFlag(false);  // mark as live
                } else {
                    // dead variable
                    varOpnd->setDeadFlag(true); // mark as dead
                    
                    if (canUnlink) {
                        if (Log::isEnabled()) {
                            Log::out() << "removing dead VarOpnd ";
                            varOpnd->print(Log::out());
                            Log::out() << ::std::endl;
                        }
                        opndManager.deleteVar(varOpnd); // remove from list
                    }
                    
                    // get the new head; this should usually be nextVar, but may be 0.
                    varOpnd0 = opndManager.getVarOpnds();
                    if (!nextVar && !varOpnd0) nextVar = varOpnd; // if it is 0, make sure we still stop
                }
                varOpnd = nextVar;
            };
            // we may have deleted all vars already, be careful here.
            if (varOpnd0) {
                varOpnd = varOpnd0->getNextVarOpnd();
                while (varOpnd != varOpnd0) {
                    VarOpnd *nextVar = varOpnd->getNextVarOpnd();
                    if (usefulVarSet.getBit(varOpnd->getId()) == true){
                        // live variable
                        varOpnd->setDeadFlag(false);  // mark as live
                    } else {
                        // dead variable

                        varOpnd->setDeadFlag(true); // mark as dead
                        if (canUnlink) {
                            if (Log::isEnabled()) {
                                Log::out() << "removing dead VarOpnd ";
                                varOpnd->print(Log::out());
                                Log::out() << ::std::endl;
                            }
                            opndManager.deleteVar(varOpnd); // remove from list
                        }
                    }
                    varOpnd = nextVar;
                }
            }
        }
    }

    {
        AutoTimer t(dcePhase6Timer); 
        flowGraph.mergeAdjacentNodes();       
    }
    {
        AutoTimer t(dcePhase5Timer); 
        if (!keepEmptyNodes) {
            //
            // Purge empty nodes.
            //
            flowGraph.purgeEmptyNodes(preserveCriticalEdges);
        }
    }

}

//
// Leave one PseudoThrow instruction only for those loops which
// do not contain other dispatch edges exiting the loop.
//
void
DeadCodeEliminator::removeExtraPseudoThrow() {
    MemoryManager memManager("DeadCodeEliminator::removeExtraPseudoThrow");

    OptPass::computeLoops(irManager);
    LoopTree* loopTree = irManager.getLoopTree();
    assert(loopTree && loopTree->isValid());

    if (Log::isLogEnabled(LogStream::DOTDUMP)) {
        OptPass::printDotFile(irManager, Log::getStageId(), "rept", "after_loop_tree");
        OptPass::printHIR(irManager);
    }

    // Nodes containing essential PseudoThrow instructions
    BitSet essentialNodes(memManager, flowGraph.getMaxNodeId());
    
    if (loopTree->hasLoops()) {
        LoopNode* loopNode = ((LoopNode*)loopTree->getRoot())->getChild();
        markEssentialPseudoThrows(loopNode, essentialNodes);
    }

    const Nodes& cfgNodes = flowGraph.getNodes();
    if (Log::isEnabled()) {
        Log::out() << "Removing useless PseudoThrow instructions:" << std::endl;
    }
    for (Nodes::const_iterator it = cfgNodes.begin(), end = cfgNodes.end(); it!=end; ++it) {
        Node* node = *it;
        Inst* lastInst = (Inst*)node->getLastInst();
        if (!essentialNodes.getBit(node->getId()) && (lastInst->getOpcode() == Op_PseudoThrow)) {
            if (Log::isEnabled()) {
                Log::out() << "  Removing instruction: ";
                lastInst->print(Log::out());
                Log::out() << std::endl;
            }
            lastInst->unlink();
            Edge* dispatchEdge = node->getExceptionEdge();
            assert(dispatchEdge != NULL);
            flowGraph.removeEdge(dispatchEdge);
        }
    }
    if (Log::isEnabled()) {
        Log::out() << "Done." << std::endl;
    }
    eliminateUnreachableCode();
}

void
DeadCodeEliminator::markEssentialPseudoThrows(LoopNode* loopNode, BitSet& essentialNodes) {
    LoopNode* childNode = loopNode->getChild();
    if (childNode != NULL)
        markEssentialPseudoThrows(childNode, essentialNodes);
    LoopNode* siblingNode = loopNode->getSiblings();
    if (siblingNode != NULL)
        markEssentialPseudoThrows(siblingNode, essentialNodes);
    if (Log::isEnabled()) {
        Log::out() << "Analyzing loop nodes with the loop header ID: "
            << loopNode->getHeader()->getId() << std::endl;
    }
    Node* mbEssentialNode = NULL;
    const Nodes& loopNodes = loopNode->getNodesInLoop();
    for (Nodes::const_iterator it = loopNodes.begin(), end = loopNodes.end(); it!=end; ++it) {
        Node* node = *it;
        if (Log::isEnabled()) {
            Log::out() << "Analyzing Node ID: " << node->getId() << std::endl;
        }
        if (!node->isBlockNode()) continue;
        Edge* exceptionEdge = node->getExceptionEdge();
        while (exceptionEdge != NULL) {
            Node* targetNode = exceptionEdge->getTargetNode();
            if (Log::isEnabled()) {
                Log::out() << "  inspecting dispatch edge to node: " << targetNode->getId() << std::endl;
            }
            if (!loopNode->inLoop(targetNode)) break;
            exceptionEdge = targetNode->getExceptionEdge();
        }
        if (exceptionEdge != NULL) {
            if (Log::isEnabled()) {
                Log::out() << " Loop exit exception edge detected: ";
            }
            if (((Inst*)node->getLastInst())->getOpcode() == Op_PseudoThrow) {
                if (essentialNodes.getBit(node->getId())) {
                    // There is an essential PseudoThrow instruction in this loop
                    if (Log::isEnabled()) {
                        Log::out() << " essential PseudoThrow inst" << std::endl;
                    }
                    return;
                } else {
                    // A candidate to essential nodes
                    if (Log::isEnabled()) {
                        Log::out() << " essential candidate" << std::endl;
                    }
                    mbEssentialNode = node;
                }
            } else {
                // No essential PseudoThrow insts in this loop
                if (Log::isEnabled()) {
                    Log::out() << " PseudoThrow killer inst" << std::endl;
                }
                return;
            }
        }
    }
    if (mbEssentialNode != NULL) {
        essentialNodes.setBit(mbEssentialNode->getId());
        if (Log::isEnabled()) {
            Log::out() << "Found essential PseudoThrow in node ID: "
                << mbEssentialNode->getId() << std::endl;
        }
    }
    return;
}

void DeadCodeEliminator::createLoop2DispatchMapping(ControlFlowGraph& cfg, InfiniteLoopsInfo& info) {
    LoopTree* lt = cfg.getLoopTree();
    if (!lt->isValid()) {
        lt->rebuild(false, true);
    }
    info.hasLoops = lt->hasLoops();
    if (!info.hasLoops) {
        return;
    }

    //algorithm: 
    //for every loop find ANY node in a loop with dispatch edge that leads out of the loop
    //add the dispatch node to the mapping. Add nothing if dispatch is unwind
    //ANY dispatch is suitable to be used for infinite loop, because the point of interruption of infinite loop is undefined.
    const Nodes& nodes = cfg.getNodes();
    for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) {
        Node* node = *it;
        if (lt->getLoopDepth(node) == 0) {
            continue;
        }
        Edge* exceptionEdge = node->getExceptionEdge();
        if (exceptionEdge == NULL) {
            continue;
        }
        Node* dispatch = exceptionEdge->getTargetNode();
        Node* loopHead = lt->getLoopHeader(node, false);
        while (dispatch && lt->getLoopHeader(dispatch, false) == loopHead) {
            dispatch = dispatch->getExceptionEdgeTarget();
        }
        if (dispatch) {
            info.map[loopHead] = dispatch;
        }
    }
}

void DeadCodeEliminator::fixInfiniteLoops(IRManager& irm, const InfiniteLoopsInfo& info) {
    if (!info.hasLoops) {
        return;
    }
    //Find infinite loops and use mapping provided to add pseudoThrows.
    //To find infinite loops use dominator trees: 
    //    LoopHead == dominates on incoming edge source. 
    //    Infinite loop == LoopHead with no paths to Exit node: when Exit node does not postdominate on LoopHead
    if (Log::isEnabled()) {
        Log::out()<<"Performing infinite loops check "<<std::endl;
    }

    ControlFlowGraph& cfg = irm.getFlowGraph();
    MemoryManager tmpMM("fixInfiniteLoops");
    OptPass::computeDominators(irm);
    DominatorTree* dom = irm.getDominatorTree();
    DominatorBuilder db;
    DominatorTree* postDom = db.computeDominators(tmpMM, &cfg, true, true);

    Node* exitNode = cfg.getExitNode();
    Nodes infiniteLoopHeads(tmpMM);

    //searching for infinite loops
    Nodes nodes(tmpMM);
    cfg.getNodes(nodes);
    for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) {
        Node* node = *it;
        if (postDom->dominates(exitNode, node)) { //the node is reachable from Exit node
            continue;
        }
        //ok, this is dead code or endless loop -> check if this is a loop
        const Edges& inEdges = node->getInEdges();
        for (Edges::const_iterator eit = inEdges.begin(), eend = inEdges.end(); eit !=eend; eit++) {
            Edge* edge = *eit;
            Node* srcNode = edge->getSourceNode();
            if (dom->dominates(node, srcNode)) { //ok, this is loop head
                infiniteLoopHeads.push_back(node);
                break;
            }
        }
    }
    
    //fixing infinite loops
    for (Nodes::const_iterator it = infiniteLoopHeads.begin(), end = infiniteLoopHeads.end(); it!=end; ++it) {
        Node* node = *it;
        Node* dispatch = NULL;
        StlMap<Node*, Node*>::const_iterator mit = info.map.find(node);
        if (mit!=info.map.end()) {
            dispatch = mit->second;
        } else {
            dispatch = cfg.getUnwindNode();
            if (dispatch == NULL) {
                dispatch = cfg.createDispatchNode(irm.getInstFactory().makeLabel());
                cfg.addEdge(dispatch, exitNode);
                cfg.setUnwindNode(dispatch);
            }
        }
        assert(dispatch!=NULL);
        cfg.splitNodeAtInstruction(node->getFirstInst(), true, false, irm.getInstFactory().makeLabel());
        node->appendInst(irm.getInstFactory().makePseudoThrow());
        cfg.addEdge(node, dispatch);
        if (Log::isEnabled()) {
            Log::out() <<"  Found infinite loop: node:";FlowGraph::print(Log::out(), node); Log::out()<<std::endl;
            Log::out() <<"      connecting loop to :";FlowGraph::print(Log::out(), dispatch); Log::out()<<std::endl;
        }
    }
    
    if (Log::isEnabled()) {
        Log::out()<<"Infinite loops check finished."<<std::endl;
    }

}


} //namespace Jitrino