/*
 *  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 copyrighashTable 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.
 */


/*
 * NOTE: The code below is based on ideas from the paper "Operator Strength
 * Reduction" by Keith D. Cooper, L.Taylor Simpson, Christopher Vick. However
 * there are some differences between original alogorithm and the
 * implementation: 
 *
 * 1. We do not traverse SSA graph, but rely on "lazy" detection of induction
 * variables 
 *
 * 2. The first step is not an SCC-detection, but CFG traversal that finds
 * instruction of the following type: mul(iv, rc) or mul(rc, iv), (where iv -
 * induction variable, rc - region constant, which is understood as loop
 * invariant) and stores them uint32o cands vector. 
 *
 * 3. Useful step that prevents degradation: check if the induction variable is
 * used as array subscript in the loop.  If such a check returns true, we do not
 * perform an optimization. The reasoning behind is the following: we will not
 * be able to remove an old inductio variable in a case when it is used as an
 * array subcsript. Even though our tranformation will reduce mul, it will
 * increase register pres * sure and lengthen codepath. It's better to avoid
 * such effects 
 *
 * 4. Then we perform apply/reduce process to the instruction stored in cands
 * vector.
 *
 * On complexity: OSR performs depth first search on each step - generally the
 * complexity of this algorithm is exponential. However the SSA graphs are
 * usually sparse, thus the results are no harder than quadratic complexity so,
 * this otimization does not slow down the compilation in any noticable rate.   
 */

#include "osr.h"
#include "deadcodeeliminator.h"

namespace Jitrino {

DEFINE_SESSION_ACTION(OSRPass, osr, "Operator Strength Reduction")

static U_32 signof(int v){ return (v == 0) ? 0 : (v < 0 ? -1 : 1);}


/* The code below is based on loop_unroll processOpnd function. However it
 * gathers some additional OSR-specific information which is obsolele for
 * loop_unroll. 
 *
 * TODO: create flexible mechanism for gathering info on the operands which
 * would help to avoid code duplication from the one hand, and be customizable
 * from another hand 
 */
OSROpndInfo OSRInductionDetector::processOpnd(LoopTree* tree,
                                      LoopNode* loopHead,
                                      InstStack& defStack,
                                      const Opnd* opnd,
                                      iv_detection_flag flag){
    if (Log::isEnabled()) {
        Log::out() << "Processing opnd: ";
        opnd->print(Log::out());
        Log::out() << "\n";
    }

    OSROpndInfo result;
    Inst* defInst = opnd->getInst();

    if (std::find(defStack.begin(), defStack.end(), defInst) !=
        defStack.end()) {
        result.setType(OSROpndInfo::COUNTER);
        result.setIncrement(0);
        result.setOpnd((Opnd*) opnd);
        return result;
    }

    Opcode opcode = defInst->getOpcode();

    if (opcode == Op_LdConstant) {
        result.setType(OSROpndInfo::LD_CONST);
        result.setConst(defInst->asConstInst()->getValue().i4);
        result.setOpnd((Opnd*) opnd);
        result.setHeader((Opnd*) opnd);
        result.setHeaderFound();
        return result;
    }

    if (!inExactLoop(tree, (Opnd*) opnd, loopHead)) {
        result.setOpnd((Opnd*) opnd);
        result.setHeader((Opnd*) opnd);
        result.setHeaderFound();
        return result;
    }

    defStack.push_back(defInst);

    if (opcode == Op_Phi) {
        OSROpndInfo info1 =
            processOpnd(tree, loopHead, defStack, defInst->getSrc(0));

        if (defInst->getNumSrcOperands() > 1) {
            OSROpndInfo info2 =
                processOpnd(tree, loopHead, defStack, defInst->getSrc(1));
            if ( ((info1.isCounter() && !info1.isPhiSplit())
                   && (info2.isDOL() || info2.isLDConst()))
                 || ((info2.isCounter() && !info2.isPhiSplit())
                   && (info1.isDOL() || info1.isLDConst())) ) {

                result.setType(OSROpndInfo::COUNTER);
                result.setIncrement(info1.isCounter()? info1.
                                    getIncrement() : info2.getIncrement());
                result.markPhiSplit();
                result.setHeader((Opnd*) opnd);
                result.setHeaderFound();
            } else if ((flag == CHOOSE_MAX_IN_BRANCH) && info1.isCounter()
                       && info2.isCounter()
                       && signof(info1.getIncrement()) ==
                       signof(info2.getIncrement())) {

                result.setType(OSROpndInfo::COUNTER);
                result.setIncrement(std::abs(info1.getIncrement()) >
                                    std::abs(info2.getIncrement())? info1.
                                    getIncrement() : info2.getIncrement());
                result.markPhiSplit();
                result.setHeader((Opnd*) opnd);
                result.setHeaderFound();
            } else {
                result.setType(OSROpndInfo::UNDEF);
            }
        }
    } else if (opcode == Op_Add || opcode == Op_Sub) {
        Opnd* opnd1 = defInst->getSrc(0);
        Opnd* opnd2 = defInst->getSrc(1);
        OSROpndInfo info1 = processOpnd(tree, loopHead, defStack, opnd1);
        OSROpndInfo info2 = processOpnd(tree, loopHead, defStack, opnd2);

        if ((info1.isLDConst() || info1.isDOL())
            && (info2.isLDConst() || info2.isDOL())) {
            if (info1.isLDConst() && info2.isLDConst()
                && info1.getConst() == info2.getConst()) {
                result.setType(OSROpndInfo::LD_CONST);
                result.setConst(info1.getConst());
                writeHeaderToResult(result, tree, info1, info2);
            }
        } else if ((info1.isCounter() && info2.isLDConst())
                   || (info2.isCounter() && info1.isLDConst())) {
            U_32 increment = info1.isCounter() ?
                info1.getIncrement() : info2.getIncrement();
            U_32 diff = info1.isLDConst()? info1.getConst() : info2.getConst();
            bool monotonousFlag = increment == 0 || diff == 0
                || (opcode == Op_Add && signof(diff) == signof(increment))
                || (opcode == Op_Sub && signof(diff) != signof(increment));
            if (monotonousFlag) {
                result.setType(OSROpndInfo::COUNTER);
                if ((info1.isCounter() && info1.isPhiSplit()) ||
                    (info2.isCounter() && info2.isPhiSplit())) {
                    result.markPhiSplit();
                    writeHeaderToResult(result, tree, info1, info2);
                }
                if (opcode == Op_Add) {
                    result.setIncrement(increment + diff);
                    writeHeaderToResult(result, tree, info1, info2);
                } else {
                    result.setIncrement(increment - diff);
                    writeHeaderToResult(result, tree, info1, info2);
                }
            } else {
                result.setType(OSROpndInfo::UNDEF);
            }
        } else {
            result.setType(OSROpndInfo::UNDEF);
        }
    } else if (opcode == Op_StVar || opcode == Op_LdVar) {
        Opnd* newOpnd = defInst->getSrc(0);
        result = processOpnd(tree, loopHead, defStack, newOpnd);
    } else if (opcode == Op_TauArrayLen) {
        Opnd* arrayOpnd = defInst->getSrc(0);
        result = processOpnd(tree, loopHead, defStack, arrayOpnd);
    } else {
        result.setType(OSROpndInfo::UNDEF);
    }

    defStack.pop_back();
    result.setOpnd((Opnd*) opnd);
    return result;
}

bool OSRInductionDetector::inExactLoop(LoopTree* tree, Opnd* opnd,
                                       LoopNode* curnode){
    LoopNode* lnode = tree->getLoopNode(opnd->getInst()->getNode(), false);
    if (lnode == 0) {
        return false;
    } else if (lnode == curnode) {
        return true;
    }
    return false;
}

bool OSRInductionDetector::inLoop(LoopTree* tree, Opnd* opnd){
    LoopNode* lnode = tree->getLoopNode(opnd->getInst()->getNode(), false);
    if (lnode == 0) {
        return false;
    }
    return true;
}

void OSRInductionDetector::writeHeaderToResult(OSROpndInfo& result,
                                               LoopTree* tree,
                                               OSROpndInfo info1,
                                               OSROpndInfo info2){
    if (result.isCounter()) {
        bool opnd1_in_loop = inLoop(tree, info1.getOpnd());
        bool opnd2_in_loop = inLoop(tree, info2.getOpnd());
        if (opnd1_in_loop) {
            result.setHeader(info1.getHeader());
        } else if (opnd2_in_loop) {
            result.setHeader(info2.getHeader());
        }
        result.setHeaderFound();

    } else {
        if (info2.isHeaderFound()) {
            result.setHeader(info2.getHeader());
            result.setHeaderFound();
        } else if (info1.isHeaderFound()) {
            result.setHeader(info1.getHeader());
            result.setHeaderFound();
        }
    }
}

OSR::OSR(IRManager & irManager0, 
         MemoryManager & memManager, 
         LoopTree* loop_Tree, 
         DominatorTree* dtree): iv(0),
                                 rc(0),
                                 irManager(irManager0),
                                 mm(memManager),
                                 loopTree(loop_Tree),
                                 hashTable(new CSEHashTable(memManager)),
                                 dominators(dtree),
                                 leading_operands(memManager),
                                 addedOpnds(memManager), 
                                 cands(memManager),
                                 LFTRHashMap(memManager){}

void OSRPass::_run(IRManager & irm){
    splitCriticalEdges(irm);
    computeDominatorsAndLoops(irm);
    LoopTree* loopTree = irm.getLoopTree();
    DominatorTree* dominatorTree = irm.getDominatorTree();
    OSR osr(irm, irm.getMemoryManager(), loopTree, dominatorTree);
    osr.runPass();
}

void OSR::recordIVRC(Inst* inst){

    if (Log::isEnabled()) {
        Log::out() << "Processing: ";
        inst->print(Log::out());
        Log::out() << "\n";
    }

    Opnd* opnd1 = inst->getSrc(0);
    Opnd* opnd2 = inst->getSrc(1);

    LoopNode* lnode = loopTree->getLoopNode(inst->getNode(), false);
    if (lnode == 0)
        return;

    OSRInductionDetector::InstStack defstack(mm);
    OSROpndInfo info1 = OSRInductionDetector::processOpnd(loopTree, lnode, defstack, opnd1);
    OSROpndInfo info2 = OSRInductionDetector::processOpnd(loopTree, lnode, defstack,opnd2);

    if (Log::isEnabled()) {
        info1.print(Log::out());
        info2.print(Log::out());

    }
    if (info1.isCounter() && (info2.isLDConst() || info2.isDOL())) {
        iv = (SsaOpnd*) info1.getOpnd();
        rc = (SsaOpnd*) info2.getOpnd();
        bool no_array = isNoArrayInLoop(lnode, iv);
        if (no_array) {
            writeLeadingOperand((SsaOpnd*) opnd1,
                                (SsaOpnd*) info1.getHeader());
        } else {
            iv = 0;
            rc = 0;
        }
    } else if (info2.isCounter() && (info1.isLDConst() || info1.isDOL())) {
        iv = (SsaOpnd*) info2.getOpnd();
        rc = (SsaOpnd*) info1.getOpnd();

        bool no_array = isNoArrayInLoop(lnode, iv);

        if (no_array) {
            writeLeadingOperand((SsaOpnd*) opnd2,
                                (SsaOpnd*) info2.getHeader());
        } else {
            iv = 0;
            rc = 0;
        }
    }
}

bool OSR::isNoArrayInLoop(LoopNode* lnode, SsaOpnd* iv){
    Nodes nodes = lnode->getNodesInLoop();
    StlVector < Node* >::iterator iter = nodes.begin(), end = nodes.end();

    for (; iter != end; iter++) {
        Node* node = *iter;
        Inst* last_inst = (Inst*) node->getLastInst();

        for (Inst* iter1 = (Inst*) node->getFirstInst();
             iter1 != last_inst; iter1 = iter1->getNextInst()) {
            Inst inst = *iter1;
            if (inst.getOpcode() == Op_AddScaledIndex) {
                Opnd* opnd = inst.getSrc(1);
                findLeadingOpnd(&inst, (SsaOpnd*) opnd);
                SsaOpnd* lop = getLeadingOperand((SsaOpnd*) opnd);
                if (lop != 0) {
                    SsaOpnd* ivlop = getLeadingOperand(iv);
                    if (lop == ivlop) {
                        return false;
                    }

                }

            }
        }
    }
    return true;
}

void OSR::writeInst(Inst* inst){
    Opcode opcode = inst->getOpcode();
    if (opcode == Op_Mul) {
        recordIVRC(inst);
        if (iv != 0 && rc != 0) {
            reduceCand red_c((SsaOpnd*) inst->getDst(), iv, rc);
            cands.push_back(red_c);
        }
        iv = 0;
        rc = 0;
    }
}

void OSR::runPass(){
    StlVector < Node* >nodes(mm);
    ControlFlowGraph& flowgraph = irManager.getFlowGraph();
    flowgraph.getNodes(nodes);

    StlVector < Node* >::iterator iter = nodes.begin(), end = nodes.end();

    for (; iter != end; iter++) {
        Node* node = *iter;
        Inst* last_inst = (Inst*) node->getLastInst();

        for (Inst* iter1 = (Inst*) node->getFirstInst();
             iter1 != last_inst; iter1 = iter1->getNextInst()) {
            writeInst(iter1);
        }
    }

    StlVector < reduceCand >::iterator viter = cands.begin();
    StlVector < reduceCand >::iterator vend = cands.end();

    for (; viter != vend; viter++) {
        reduceCand rcand = *viter;
        replace(rcand.dst, rcand.iv, rcand.rc);
    }

    StlVector < Node* >nnodes(mm);
    ControlFlowGraph& ffg = irManager.getFlowGraph();
    ffg.getNodes(nnodes);
    replaceLinearFuncTest(nnodes);

}

void OSR::writeLeadingOperand(SsaOpnd* opnd, SsaOpnd* header){
    leading_operands[opnd] = header;
    if (Log::isEnabled()) {
        Log::out() << "Header of: " << std::endl;
        opnd->print(Log::out());
        Log::out() << "is" << std::endl;
        if (header) {
            header->print(Log::out());
            Log::out() << std::endl;
        } else {
            Log::out() << "Null" << std::endl;
        }
    }
}

SsaOpnd* OSR::getLeadingOperand(SsaOpnd* opnd){
    if (opnd == 0) {
        return 0;
    }
    SsaOpnd* result = 0;
    if (leading_operands.has(opnd)) {
        result = leading_operands[opnd];
    }
    return result;
}

void OSR::replace(SsaOpnd* opnd, SsaOpnd* iv, SsaOpnd* rc){
    Inst* inst = opnd->getInst();
    SsaOpnd* dstInst = reduce(inst->getDst()->getType(), inst->getOpcode(),
                              inst->getOperation(), iv, rc);
    Inst* copyInst = irManager.getInstFactory().makeCopy(opnd, dstInst);
    copyInst->insertBefore(inst);
    inst->unlink();
    writeLeadingOperand(opnd, getLeadingOperand(iv));

}

Inst* OSR::insertNewDef(Type* type, SsaOpnd* iv, SsaOpnd* rc){
    Inst* inst = copyInst(type, iv->getInst(), rc,
                          Operation(iv->getInst()->getOpcode()));
    insertInst(inst, iv->getInst());
    return inst;
}

void OSR::findLeadingOpnd(Inst* newDef, SsaOpnd* opnd){
    Node* node = newDef->getNode();
    LoopNode* lnode = this->loopTree->getLoopNode(node, false);
    OSRInductionDetector::InstStack newstack(this->mm);
    OSROpndInfo oinfo = OSRInductionDetector::processOpnd(loopTree, lnode, newstack, opnd);
    if (oinfo.isHeaderFound()) {
        writeLeadingOperand(opnd, (SsaOpnd*) oinfo.getHeader());
    }
}

void OSR::replaceOperand(U_32 num, Inst* inst, SsaOpnd* opnd,
                         Opnd* iv_lead, Node* iv_lead_node,
                         Type* type, Opcode opcode, SsaOpnd* rc,
                         Operation op){
    findLeadingOpnd(inst, opnd);
    SsaOpnd* opnd_header = getLeadingOperand(opnd);
    Node* opnd_headerNode = 0;

    if (opnd_header != 0) {
        opnd_headerNode = opnd_header->getInst()->getNode();
    }

    if ((iv_lead != 0) && (opnd_headerNode == iv_lead_node)) {
        inst->setSrc(num, reduce(type, opcode, op, opnd, rc));
    } else if ((opcode == Op_Mul) || (inst->getOpcode() == Op_Phi)) {
        SsaOpnd* newOpnd = apply(type, opcode, op, opnd, rc);
        if (opnd->isSsaVarOpnd()) {
            newOpnd = makeVar(newOpnd, inst->getDst()->asSsaVarOpnd(),
                              opnd->getInst());
        } else {
            newOpnd = makeTmp(newOpnd->asSsaOpnd(), opnd->getInst());
        }
        inst->setSrc(num, newOpnd);
    }
}

void OSR::replaceOperands(Type* type, Inst* inst, SsaOpnd* iv,
                          SsaOpnd* rc, Opcode opcode, Operation op){

    if (Log::isEnabled()) {
        Log::out() << "Replacing operands" << std::endl;
        Log::out() << "RC" << std::endl;
        rc->print(Log::out());
        Log::out() << "IV" << std::endl;
        iv->print(Log::out());
        Log::out() << std::endl;
    }

    U_32 numOpnds = inst->getNumSrcOperands();
    SsaOpnd* iv_lead = getLeadingOperand(iv);
    Node* iv_lead_node = iv_lead->getInst()->getNode();
    for (U_32 num = 0; num < numOpnds; num++) {
        SsaOpnd* opnd = inst->getSrc(num)->asSsaOpnd();
        replaceOperand(num, inst, opnd, iv_lead, iv_lead_node, type,
                       opcode, rc, op);
    }

}

SsaOpnd* OSR::reduce(Type* type, Opcode opcode, Operation op,
                     SsaOpnd* iv, SsaOpnd* rc){
    if (Log::isEnabled()) {
        Log::out() << "Reducing: ";
        iv->print(Log::out());
        Log::out() << std::endl;
        rc->print(Log::out());
        Log::out() << std::endl;
    }
    Inst* newinst = hashTable->lookup(op.encodeForHashing(), iv->getId(), rc->getId());
    if (!newinst) {
        Inst* newDef = insertNewDef(type, iv, rc);
        if (Log::isEnabled()) {
            Log::out() << "NewDef" << std::endl;
            newDef->print(Log::out());
            Log::out() << std::endl;
        }

        SsaOpnd* result = newDef->getDst()->asSsaOpnd();
        writeLeadingOperand(result, getLeadingOperand(iv));
        hashTable->insert(op.encodeForHashing(), iv->getId(),
                          rc->getId(), newDef);
        writeLFTR(iv, op, rc, newDef->getDst()->asSsaOpnd());
        replaceOperands(type, newDef, iv, rc, opcode, op);
        return result;

    } else {
        SsaOpnd* result = newinst->getDst()->asSsaOpnd();
        return result;
    }
}

Inst* OSR::copyInst(Type* type, Inst* oldDef, SsaOpnd* rc, Operation op){
    Inst* newDef = 0;
    SsaOpnd* old = oldDef->getDst()->asSsaOpnd();
    if (old->isSsaVarOpnd()) {
        newDef = createNewVarInst(old, type, oldDef, rc, op);
    } else {
        InstFactory& instFactory = irManager.getInstFactory();
        OpndManager& opndManager = irManager.getOpndManager();
        OpndRenameTable opndRenameTable(mm);
        newDef = instFactory.clone(oldDef, opndManager, &opndRenameTable);
        newDef->getDst()->setType(type);
        newDef->setType(type->tag);
    }
    return newDef;
}

Inst* OSR::createNewVarInst(SsaOpnd* old, Type* type,
                            Inst* old_inst, SsaOpnd* rc, Operation op){
    InstFactory& instFactory = irManager.getInstFactory();
    OpndManager& opndManager = irManager.getOpndManager();

    VarOpnd* oldVar = old->asSsaVarOpnd()->getVar();
    VarOpnd* newVar = createOperand(type, oldVar, rc, op);
    SsaVarOpnd* newSsaVar = opndManager.createSsaVarOpnd(newVar);
    if (old_inst->getOpcode() == Op_StVar) {
        return instFactory.makeStVar(newSsaVar,
                                     old_inst->getSrc(0)->asSsaOpnd());
    } else {
        U_32 num = old_inst->getNumSrcOperands();
        Opnd** newOpnds = new(mm) Opnd* [num];
        for (U_32 i = 0; i < num; i++) {
            newOpnds[i] = old_inst->getSrc(i)->asSsaOpnd();
        }
        return (PhiInst*)instFactory.makePhi(newSsaVar, num, newOpnds);
    }
}

void OSR::insertInst(Inst* inst, Inst* place){
    if (inst->getOpcode() == Op_Phi || place->getOpcode() != Op_Phi) {
        inst->insertAfter(place);
    } else {
        do {
            place = (Inst*) place->next();
        }
        while ((place != 0) && (place->getOpcode() == Op_Phi));
        if (place != 0) {
            inst->insertBefore(place);
        }
    }
}

SsaOpnd* OSR::apply(Type* type, Opcode opcode, Operation op,
                    SsaOpnd* opnd1, SsaOpnd* opnd2){
    SsaOpnd* opnd2Leader = getLeadingOperand(opnd2);
    if (opnd2Leader!= 0) {
        opnd2 = opnd2Leader;
    }

    opnd1 = (SsaOpnd*) DeadCodeEliminator::copyPropagate(opnd1);

    if (Log::isEnabled()) {
        Log::out() << "Applying: ";
        opnd1->print(Log::out());
        Log::out() << std::endl;
        opnd2->print(Log::out());
        Log::out() << std::endl;
    }

    Inst* newinst =
        hashTable->lookup(op.encodeForHashing(), opnd1->getId(),
                          opnd2->getId());
    SsaOpnd* result = 0;
    if (newinst) {
        result = newinst->getDst()->asSsaOpnd();
    } else {
        if (getLeadingOperand(opnd1) && isLoopInvariant(opnd2)) {
            result = reduce(type, opcode, op, opnd1, opnd2);
        } else if (getLeadingOperand(opnd2) && isLoopInvariant(opnd1)) {
            result = reduce(type, opcode, op, opnd2, opnd1);
        } else {
            OpndManager & opndManager = irManager.getOpndManager();
            result = opndManager.createSsaTmpOpnd(type);
            InstFactory & instFactory = irManager.getInstFactory();
            opnd1 = makeTmp(opnd1, opnd1->getInst());
            opnd2 = makeTmp(opnd2, opnd2->getInst());

            Inst* newInst = instFactory.makeInst(opcode, op.getModifier(), type->tag,
                                                 result, opnd1, opnd2);
            Inst* instLoc = findInsertionPlace(opnd1, opnd2);
            insertInst(newInst, instLoc);
            writeLeadingOperand(result, 0);
            hashTable->insert(op.encodeForHashing(), opnd1->getId(),
                              opnd2->getId(), newInst);
            writeLFTR(opnd1, op, opnd2, newInst->getDst()->asSsaOpnd());

        }
    }
    return result;
}
Inst* OSR::findInsertionPlace(SsaOpnd* opnd1, SsaOpnd* opnd2){

    findLeadingOpnd(opnd2->getInst(), opnd2);
    SsaOpnd* opnd2Leader = getLeadingOperand(opnd2);
    if (opnd2Leader!= 0) {
      opnd2 = opnd2Leader;
    }

    Inst* opnd1inst = opnd1->getInst();
    Inst* opnd2inst = opnd2->getInst();
    Node* block1 = opnd1inst->getNode();
    Node* block2 = opnd2inst->getNode();
    Inst* place = 0;
    if (block1 == block2) {
        Inst* i = opnd1inst;
        place = opnd2inst;
        while (!i->isLabel()) {
            if (i == opnd2inst) {
                place = opnd1inst;
                break;
            }
            i = i->getPrevInst();
        }
    } else if ((block1 != 0) && (dominators->dominates(block1, block2))) {
        place = opnd2inst;
    } else {
        place = opnd1inst;
    }
    return place;
}

SsaTmpOpnd* OSR::makeTmp(SsaOpnd* inOpnd, Inst* place){
    if (inOpnd->isSsaVarOpnd()) {
        SsaVarOpnd* inSsaVarOpnd = inOpnd->asSsaVarOpnd();
        Inst* inst = inSsaVarOpnd->getInst();
        if (inst->getOpcode() == Op_StVar) {
            SsaTmpOpnd* res = inst->getSrc(0)->asSsaTmpOpnd();
            return res;
        } else {
            OpndManager& opndManager = irManager.getOpndManager();
            InstFactory& instFactory = irManager.getInstFactory();

            SsaTmpOpnd* res = opndManager.createSsaTmpOpnd(inOpnd->getType());
            Inst* ldVarInst = instFactory.makeLdVar(res, inSsaVarOpnd);
            Inst* where = chooseLocationForConvert(inst, place);
            insertInst(ldVarInst, where);
            writeLeadingOperand(res, getLeadingOperand(inOpnd));
            return res;
        }
    } else {
        return inOpnd->asSsaTmpOpnd();
    }
}

SsaVarOpnd* OSR::makeVar(SsaOpnd* inOpnd, SsaVarOpnd* var, Inst* place){

    if (inOpnd->isSsaTmpOpnd()) {
        Inst* inst = inOpnd->getInst();
        if (inst->getOpcode() == Op_LdVar) {
            SsaVarOpnd* res = inst->getSrc(0)->asSsaVarOpnd();
            return res;
        } else {
            OpndManager& opndManager = irManager.getOpndManager();
            InstFactory& instFactory = irManager.getInstFactory();

            SsaVarOpnd* res = opndManager.createSsaVarOpnd(var->getVar());
            Inst* stVarInst = instFactory.makeStVar(res, inOpnd);

            Inst* where = chooseLocationForConvert(inst, place);
            insertInst(stVarInst, where);
            writeLeadingOperand(res, getLeadingOperand(inOpnd));
            return res;
        }
    } else {
        return inOpnd->asSsaVarOpnd();
    }
}

Inst* OSR::chooseLocationForConvert(Inst* inst, Inst* place){
    Node* instNode = inst->getNode();
    Node* placeNode = place->getNode();
    Inst* where = 0;
    if (instNode == placeNode) {
        where = inst;
    } else {
        if (dominators->dominates(instNode, placeNode)) {
            where = place;
        } else {
            where = inst;
        }
    }
    return where;

}

VarOpnd* OSR::createOperand(Type* newType, VarOpnd * var, SsaOpnd * rc,
                            Operation op){
    OldInst g;
    g.type = newType;
    g.var = var;
    g.ssa = rc;
    Entry key(g, op);

    VarOpnd* newVar = addedOpnds[key];

    if (newVar == 0) {
        OpndManager & opndManager = irManager.getOpndManager();
        newVar = opndManager.createVarOpnd(newType, false);
        addedOpnds[key] = newVar;
    }
    return newVar;
}

bool OSR::isLoopInvariant(SsaOpnd* name){

    OSRInductionDetector::InstStack stack(this->mm);
    LoopNode* mynode = this->loopTree->getLoopNode(name->getInst()->getNode(), false);
    if (mynode == 0) {
        return false;
    }
    OSROpndInfo nameinfo = OSRInductionDetector::processOpnd(loopTree, mynode, stack, name);
    if (nameinfo.isHeaderFound()) {
        writeLeadingOperand(name, (SsaOpnd*) nameinfo.getHeader());
    }
    if (nameinfo.isDOL() || nameinfo.isLDConst()) {
        return true;
    } else {
        return false;
    }

}

void OSR::writeLFTR(SsaOpnd* iv, Operation op, SsaOpnd* loop_inv,
                    SsaOpnd* result){
    OperationSsaOpnd tmp1(op, loop_inv);
    LFTREntry tmp2(tmp1, result);
    LFTRHashMap[iv] = tmp2;
}

void OSR::replaceLinearFuncTest(StlVector < Node* >&postOrderNodes){
    StlVector < Node* >::reverse_iterator riter = postOrderNodes.rbegin(),
        rend = postOrderNodes.rend();
    for (; riter != rend; ++riter) {
        Node* node = *riter;
        Inst* labelInst = (Inst*) node->getLabelInst();

        for (Inst* iter = (Inst*) labelInst->next();
             (iter != 0 && iter != labelInst);
             iter = (Inst*) iter->next()) {
            if ((iter->getOpcode() == Op_Cmp)
                || (iter->getOpcode() == Op_Branch))
                performLFTR(iter);

        }
    }
}

void OSR::performLFTR(Inst* inst){
    Opcode opcode = inst->getOpcode();
    if (opcode == Op_Cmp || opcode == Op_Branch) {
        U_32 num = inst->getNumSrcOperands();
        if (2 == num) {
            iv = 0;
            rc = 0;
            recordIVRC(inst);
            if (iv && rc) {
                SsaOpnd* reduced = 0;
                SsaOpnd* newbound = 0;
                SsaOpnd* src = getLeadingOperand(iv);
                if (src == 0)
                    return;
                reduced = followEdges(iv);
                newbound = applyEdges(iv, rc);
                if ((reduced != src) && (newbound != rc)) {
                    reduced = makeTmp(reduced, iv->getInst());
                    newbound = makeTmp(newbound, rc->getInst());
                    inst->setType(reduced->getType()->tag);

                    if ((inst->getOpcode() == Op_Cmp
                         || inst->getOpcode() == Op_Branch)
                        && inst->getComparisonModifier() == Cmp_GT) {
                        inst->setSrc(1, reduced);
                        inst->setSrc(0, newbound);
                    } else
                        if ((inst->getOpcode() == Op_Cmp
                             || inst->getOpcode() == Op_Branch)
                            && inst->getComparisonModifier() == Cmp_GTE) {
                        inst->setSrc(0, reduced);
                        inst->setSrc(1, newbound);

                    } else {
                        inst->setSrc(1, reduced);
                        inst->setSrc(0, newbound);
                    }
                }
            }
            iv = 0;
            rc = 0;
        }
    }
}

SsaOpnd* OSR::followEdges(SsaOpnd* iv){
    if (!LFTRHashMap.has(iv)) {
        return iv;
    } else {
        LFTREntry & tmp2 = LFTRHashMap[iv];
        SsaOpnd* reduced = tmp2.second;
        return followEdges(reduced);
    }
}

SsaOpnd* OSR::applyEdges(SsaOpnd* iv, SsaOpnd* bound){
    SsaOpnd* res = 0;
    if (!LFTRHashMap.has(iv)) {
        res = bound;
    } else {
        LFTREntry & tmp2 = LFTRHashMap[iv];
        Operation op = tmp2.first.first;
        SsaOpnd* rc = tmp2.first.second;
        SsaOpnd* reduced = tmp2.second;
        Opcode opcode = op.getOpcode();
        SsaOpnd* newRC = apply(reduced->getType(), opcode, op, bound, rc);
        res = applyEdges(reduced, newRC);
    }
    return res;
}
}