/*
 *  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 "escapeanalyzer.h"
#include "Log.h"
#include "Inst.h"
#include "Dominator.h"
#include "Loop.h"
#include "globalopndanalyzer.h"
#include "optimizer.h"
#include "FlowGraph.h"

#include <algorithm>

namespace Jitrino {

DEFINE_SESSION_ACTION(LoopPeelingPass, peel, "Loop Peeling")

void
LoopPeelingPass::_run(IRManager& irm) {
    computeDominators(irm);
    DominatorTree* dominatorTree = irm.getDominatorTree();
    assert(dominatorTree->isValid());
    LoopBuilder lb(irm.getNestedMemoryManager(), irm, *dominatorTree, irm.getFlowGraph().hasEdgeProfile());
    lb.computeLoops(true);
    lb.peelLoops();
}

LoopBuilder::LoopBuilder(MemoryManager& mm, IRManager& irm, 
                         DominatorTree& d, bool useProfile) 
    : loopMemManager(mm), dom(d), irManager(irm), 
      instFactory(irm.getInstFactory()), fg(irm.getFlowGraph()), info(NULL), root(NULL), 
      useProfile(useProfile), needsSsaFixup(false), flags(*irm.getOptimizerFlags().loopBuilderFlags)
{
}

void LoopBuilder::readFlags(Action* argSource, LoopBuilderFlags* flags) {
    IAction::HPipeline p = NULL; //default pipeline for argSource
    flags->hoist_loads = argSource->getBoolArg(p, "loop.hoist_loads", false);
    flags->invert = argSource->getBoolArg(p, "loop.invert", false);
    flags->peel = argSource->getBoolArg(p, "loop.peel", true);
    flags->insideout_peeling = argSource->getBoolArg(p, "loop.insideout_peeling", false);
    flags->old_static_peeling = argSource->getBoolArg(p, "loop.old_static_peeling", false);
    flags->aggressive_peeling = argSource->getBoolArg(p, "loop.aggressive_peeling", true);
    flags->peel_upto_branch = argSource->getBoolArg(p, "loop.peel_upto_branch", true);
    flags->peeling_threshold = argSource->getIntArg(p, "loop.peeling_threshold", 2);
    flags->fullpeel = argSource->getBoolArg(p, "loop.fullpeel", false);
    flags->fullpeel_max_inst = argSource->getIntArg(p, "loop.fullpeel_max_inst", 40);
    flags->peel_upto_branch_no_instanceof = argSource->getBoolArg(p, "loop.peel_upto_branch_no_instanceof", true);

}

void LoopBuilder::showFlags(std::ostream& os) {
    os << "  loop builder flags:"<<std::endl;
    os << "    loop.hoist_loads[={on|OFF}] - peel assuming load hoisting" << std::endl;
    os << "    loop.invert[={on|OFF}]      - try to invert loops to reduce branches" << std::endl;
    os << "    loop.peel[={ON|off}]        - do peeling" << std::endl;
    os << "    loop.insideout_peeling[={on|OFF}]" << std::endl;
    os << "    loop.aggressive_peeling[={ON|off}] - be aggressive about peeling" << std::endl;
    os << "    loop.peel_upto_branch[={on|OFF}]   - peel only up to a branch" << std::endl;
    os << "    loop.old_static_peeling[={on|OFF}] - use old-style peeling for static runs" << std::endl;
    os << "    loop.peeling_threshold[=int]  - (default 2)" << std::endl;
    os << "    loop.peel_upto_branch_no_instanceof[={on|OFF}] - with peel_upto_branch, peel only up to a branch or instanceof" << std::endl;
}

template <class IDFun>
class LoopMarker {
public:
    static U_32 markNodesOfLoop(StlBitVector& nodesInLoop, Node* header, Node* tail);
private:
    static U_32 backwardMarkNode(StlBitVector& nodesInLoop, Node* node, StlBitVector& visited);
    static U_32 countInsts(Node* node);
};

template <class IDFun>
U_32 LoopMarker<IDFun>::countInsts(Node* node) {
    U_32 count = 0;
    Inst* first = (Inst*)node->getFirstInst();
    if (first != NULL) {
        for(Inst* inst = first->getNextInst(); inst != NULL; inst = inst->getNextInst())
            ++count;
    }
    return count;
}

template <class IDFun>
U_32 LoopMarker<IDFun>::backwardMarkNode(StlBitVector& nodesInLoop, 
                                Node* node, 
                                StlBitVector& visited) {
    static IDFun getId;
    if(visited.setBit(node->getId()))
        return 0;

    U_32 count = countInsts(node);
    nodesInLoop.setBit(getId(node));

    const Edges& inEdges = node->getInEdges();
    Edges::const_iterator eiter;
    for(eiter = inEdges.begin(); eiter != inEdges.end(); ++eiter) {
        Edge* e = *eiter;
        count += backwardMarkNode(nodesInLoop, e->getSourceNode(), visited);
    }
    return count;
}

// 
// traverse graph backward starting from tail until header is reached
//
template <class IDFun>
U_32 LoopMarker<IDFun>::markNodesOfLoop(StlBitVector& nodesInLoop,
                               Node* header,
                               Node* tail) {
    static IDFun getId;
    U_32 maxSize = ::std::max(getId(header), getId(tail));
    MemoryManager tmm("LoopBuilder::markNodesOfLoop.tmm");
    StlBitVector visited(tmm, maxSize);

    // mark header is visited
    U_32 count = countInsts(header);
    nodesInLoop.setBit(getId(header));
    visited.setBit(header->getId());

    // starting backward traversal
    return count + backwardMarkNode(nodesInLoop, tail, visited);
}



//
// the current loop contains the header
// we traverse descendants to find who contains the header and return the 
// descendant loop
//
LoopNode* LoopBuilder::findEnclosingLoop(LoopNode* loop, Node* header) {
    for (LoopNode* l = loop->getChild(); l != NULL; l = l->getSiblings())
        if (l->inLoop(header))
            return findEnclosingLoop(l, header);

    // if no descendant contains the header then return loop
    return loop;
}



bool noStoreOrSynch(ControlFlowGraph& fg) {
    const Nodes& nodes = fg.getNodes();
    Nodes::const_iterator niter;
    for(niter = nodes.begin(); niter != nodes.end(); ++niter) {
        Node* n = *niter;
        Inst* first = (Inst*)n->getFirstInst();
        for(Inst* inst = first->getNextInst(); inst != NULL; inst = inst->getNextInst()) {
            if (inst->getOperation().isStoreOrSync()) {
                return false;
            }
        }
    }
    return true;
}

bool LoopBuilder::isVariantOperation(Operation operation) {
    if (operation.isCheck())
        return false;
    if (operation.canThrow()) {
        return true;
    }
    if (!flags.hoist_loads) {
        if (operation.isLoad())
            return true;
    }
    if (operation.isCSEable()) {
        return false;
    }
    return true;
}


bool LoopBuilder::isVariantInst(Inst* inst, StlHashSet<Opnd*>& variantOpnds) {
    Operation operation = inst->getOperation();
    Opcode op = operation.getOpcode();

    bool isfinalload = false;
    const OptimizerFlags& optimizerFlags = irManager.getOptimizerFlags();
    if (optimizerFlags.cse_final) {
        switch (inst->getOpcode()) {
        case Op_TauLdInd: 
            {
                Inst *srcInst = inst->getSrc(0)->getInst();
                if ((srcInst->getOpcode() == Op_LdFieldAddr) ||
                    (srcInst->getOpcode() == Op_LdStaticAddr)) {
                    FieldAccessInst *faInst = srcInst->asFieldAccessInst();
                    FieldDesc *fd = faInst->getFieldDesc();
                    if (fd->isInitOnly()) {

                        // first check for System stream final fields which vary
                        NamedType *td = fd->getParentType();
                        if (strncmp(td->getName(),"java/lang/System",20)==0) {
                            const char *fdname = fd->getName();
                            if ((strncmp(fdname,"in",5)==0) ||
                                (strncmp(fdname,"out",5)==0) ||
                                (strncmp(fdname,"err",5)==0)) {
                                break;
                            }
                        }

                        isfinalload = true;
                    }
                }
            } 
            break;
        case Op_LdStatic:
            {
                FieldAccessInst *inst1 = inst->asFieldAccessInst();
                assert(inst1);
                FieldDesc* fd = inst1->getFieldDesc();
                if (fd->isInitOnly()) {

                    // first check for System stream final fields which vary
                    NamedType *td = fd->getParentType();
                    if (strncmp(td->getName(),"java/lang/System",20)==0) {
                        const char *fdname = fd->getName();
                        if ((strncmp(fdname,"in",5)==0) ||
                            (strncmp(fdname,"out",5)==0) ||
                            (strncmp(fdname,"err",5)==0)) {
                            break;
                        }
                    }

                    isfinalload = true;
                }
            }
            break;
        case Op_TauLdField:
            {
                FieldAccessInst *inst1 = inst->asFieldAccessInst();
                assert(inst1);
                FieldDesc* fd = inst1->getFieldDesc();
                if (fd->isInitOnly()) {

                    // first check for System stream final fields which vary
                    NamedType *td = fd->getParentType();
                    if (strncmp(td->getName(),"java/lang/System",20)==0) {
                        const char *fdname = fd->getName();
                        if ((strncmp(fdname,"in",5)==0) ||
                            (strncmp(fdname,"out",5)==0) ||
                            (strncmp(fdname,"err",5)==0)) {
                            break;
                        }
                    }

                    isfinalload = true;
                }
            }
            break;
        default:
            break;
        };
    }

    // Inst has potential side effect
    if (isVariantOperation(operation) && !isfinalload)
        return true;

    // Is merge point.  Variant depending on incoming path.
    if (op == Op_LdVar || op == Op_Phi)
        return true;

    // Check for variant src.
    U_32 n = inst->getNumSrcOperands();
    for(U_32 i = 0; i < n; ++i) {
        Opnd* src = inst->getSrc(i);
        if (variantOpnds.find(src) != variantOpnds.end())
            return true;
    }

    return false;
}

void LoopBuilder::hoistHeaderInvariants(Node* preheader, Node* header, StlVector<Inst*>& invariantInsts) {
    assert(preheader->getOutDegree() == 1 && preheader->getOutEdges().front()->getTargetNode() == header);

    StlVector<Inst*>::iterator iiter;
    for(iiter = invariantInsts.begin(); iiter != invariantInsts.end(); ++iiter) {
        Inst* inst = *iiter;
        if (inst == header->getLastInst() && header->getOutDegree() > 1) {
            // Don't hoist control flow instruction.
            break;
        }
        inst->unlink();
        preheader->appendInst(inst);
    }
}


bool LoopBuilder::isInversionCandidate(Node* originalHeader, Node* header, StlBitVector& nodesInLoop, Node*& next, Node*& exit) {
    if(Log::isEnabled()) {
        Log::out() << "Consider rotating ";
        FlowGraph::printLabel(Log::out(), header);
        Log::out() << "  df = (" << (int) header->getDfNum() << ")" << std::endl;
    }
    assert(nodesInLoop.getBit(header->getId()));

    if (flags.aggressive_peeling) {
        if (header->getOutDegree() == 1) {
            next = header->getOutEdges().front()->getTargetNode();
            if(next->getInDegree() > 1 && next != originalHeader) {
                // A pre-header for an inner loop - do not peel.
                if (Log::isEnabled()) {
                    Log::out() << "Stop peeling node at ";FlowGraph::printLabel(Log::out(), header); Log::out()<<": preheader for inner loop. " << std::endl;
                }
                return false;
            }
            exit = NULL;
            return true;
        }
    }

    if (header->getOutDegree() != 2) {
        if (Log::isEnabled()) {
            Log::out() << "Stop peeling node at L";  FlowGraph::printLabel(Log::out(), header); Log::out() << ": no exit. " << std::endl;
        }
        return false;
    }

    Node* succ1 = header->getOutEdges().front()->getTargetNode();
    Node* succ2 = header->getOutEdges().back()->getTargetNode();
    
    // Check if either succ is an exit.
    if(nodesInLoop.getBit(succ1->getId())) {
        if(!nodesInLoop.getBit(succ2->getId())) {
            next = succ1;
            exit = succ2;
        } else {
            // Both succ's are in loop, no inversion.
            if (Log::isEnabled()) {
                Log::out() << "Stop peeling node at L";  FlowGraph::printLabel(Log::out(), header); Log::out()<< ": no exit. " << std::endl;
            }
            return false;
        }
    } else {
        // At least one succ of a header must be in the loop.
        assert(nodesInLoop.getBit(succ2->getId()));
        next = succ2;
        exit = succ1;
    }

    if(next->getInDegree() > 1 && next != originalHeader ) {
        // If next has more than one in edge, it must be the header
        // of an inner loop.  Do not peel its preheader.
        if (Log::isEnabled()) {
            Log::out()<< "Stop peeling node at L" ; FlowGraph::printLabel(Log::out(), header); Log::out() << ": preheader for inner loop. " << std::endl;
        }
        return false;
    }
    
    return true;
}

// Perform loop inversion for each recorded loop.
void LoopBuilder::peelLoops(StlVector<Edge*>& loopEdgesIn) {
    // Mark the temporaries that are local to a given basic block
    GlobalOpndAnalyzer globalOpndAnalyzer(irManager);
    globalOpndAnalyzer.doAnalysis();

    // Set def-use chains
    MemoryManager peelmem("LoopBuilder::peelLoops.peelmem");

    OpndManager& opndManager = irManager.getOpndManager();
    InstFactory& instFactory = irManager.getInstFactory();

    // Threshold at which a block is considered hot
    double heatThreshold = irManager.getHeatThreshold();

    StlVector<Edge*> loopEdges(peelmem);
    if(flags.insideout_peeling) {
        StlVector<Edge*>::reverse_iterator i = loopEdgesIn.rbegin(); while (i != loopEdgesIn.rend()) {
            loopEdges.insert(loopEdges.end(), *i);
            i++;
        }
    } else {
        StlVector<Edge*>::iterator i = loopEdgesIn.begin();
        while (i != loopEdgesIn.end()) {
            loopEdges.insert(loopEdges.end(), *i);
            i++;
        }
    }

    StlVector<Edge*>::iterator i;
    for(i = loopEdges.begin(); i != loopEdges.end(); ++i) {
        // The current back-edge
        Edge* backEdge = *i;

        // The initial header
        Node* header = backEdge->getTargetNode();
        if (header->isDispatchNode()) {
            continue;
        }
        assert(header->getInDegree() == 2);
        Node* originalInvertedHeader = header;

        // The initial loop end
        Node* tail = backEdge->getSourceNode();

        // The initial preheader
        Node* preheader = header->getInEdges().front()->getSourceNode();
        if (preheader == tail)
            preheader = header->getInEdges().back()->getSourceNode();

        // Temporary memory for peeling
        U_32 maxSize = fg.getMaxNodeId();
        MemoryManager tmm("LoopBuilder::peelLoops.tmm");
        
        // Compute nodes in loop
        StlBitVector nodesInLoop(tmm, maxSize);
        U_32 loopSize = LoopMarker<IdentifyByID>::markNodesOfLoop(nodesInLoop, header, tail);

        // Operand renaming table for duplicated nodes
        OpndRenameTable* duplicateTable = new (tmm) OpndRenameTable(tmm);

        // Perform loop inversion until header has no exit condition or 
        // until one iteration is peeled.
        Node* next;
        Node* exit;

        if (useProfile || !flags.old_static_peeling) {
            //
            // Only peel hot loops
            //
            if(useProfile) {
                double preheaderFreq = preheader->getExecCount();
                if(header->getExecCount() < heatThreshold || header->getExecCount() < preheaderFreq*flags.peeling_threshold || header->getExecCount() == 0)
                    continue;
            }
            
            //
            // Rotate loop one more time if the tail is not a branch (off by default)
            //
            Opcode op1 = ((Inst*)tail->getLastInst())->getOpcode();
            Opcode op2 = ((Inst*)header->getLastInst())->getOpcode();
            if(flags.invert && (op1 != Op_Branch) && (op2 != Op_Branch)) {
                if(isInversionCandidate(originalInvertedHeader, header, nodesInLoop, next, exit)) {
                    DefUseBuilder defUses(peelmem);
                    defUses.initialize(fg);
                    preheader = FlowGraph::tailDuplicate(irManager, preheader, header, defUses); 
                    tail = header;
                    header = next;
                    assert(tail->findTargetEdge(header) != NULL && preheader->findTargetEdge(header) != NULL);
                    if(tail->findTargetEdge(header) == NULL) {
                        tail =  tail->getUnconditionalEdge()->getTargetNode();
                        assert(tail != NULL && tail->findTargetEdge(header) != NULL);
                    }
                    originalInvertedHeader = header;
                }
            }
            
            //
            // Compute blocks to peel
            //
            Node* newHeader = header;
            Node* newTail = NULL;
            StlBitVector nodesToPeel(tmm, maxSize);
            if(flags.fullpeel) {
                if(loopSize <= flags.fullpeel_max_inst) {
                    nodesToPeel = nodesInLoop;
                    newTail = tail;
                }
            } else {
                while(isInversionCandidate(originalInvertedHeader, newHeader, nodesInLoop, next, exit)) {
                    if(Log::isEnabled()) {
                        Log::out() << "Peel ";
                        FlowGraph::printLabel(Log::out(), newHeader);
                        Log::out() << std::endl;
                    }
                    newTail = newHeader;
                    nodesToPeel.setBit(newHeader->getId());
                    newHeader = next;
                    if(newHeader == originalInvertedHeader) {
                        Log::out() << "One iteration peeled" << std::endl;
                        break;
                    }
                }
            }
            if(flags.peel) {
                header = newHeader;
                if(flags.peel_upto_branch) {
                    //
                    // Break final header at branch to peel more instructions
                    //
                    if(header != originalInvertedHeader) {
                        Inst* last = (Inst*)header->getLastInst();
                        if(header->getOutDegree() > 1)
                            last = last->getPrevInst();
                        if (flags.peel_upto_branch_no_instanceof) {
                            Inst *first = (Inst*)header->getFirstInst();
                            while ((first != last) && (first->getOpcode() != Op_TauInstanceOf)) {
                                first = first->getNextInst();
                            }
                            last = first;
                        }
                        Node* sinkNode = fg.splitNodeAtInstruction(last, true, false, instFactory.makeLabel());
                        newTail = header;
                        nodesToPeel.resize(sinkNode->getId()+1);
                        nodesToPeel.setBit(header->getId());
                        if(Log::isEnabled()) {
                            Log::out() << "Sink Node = ";
                            FlowGraph::printLabel(Log::out(), sinkNode);
                            Log::out() << ", Header = ";
                            FlowGraph::printLabel(Log::out(), header);
                            Log::out() << ", Original Header = ";
                            FlowGraph::printLabel(Log::out(), originalInvertedHeader);
                            Log::out() << std::endl;
                        }
                        header = sinkNode;
                    }
                }
                
                //
                // Peel the nodes
                //
                if(newTail != NULL) {
                    DefUseBuilder defUses(peelmem);
                    defUses.initialize(fg);
                    Edge* entryEdge = preheader->findTargetEdge(originalInvertedHeader);
                    double peeledFreq = preheader->getExecCount() * entryEdge->getEdgeProb(); 
                    Node* peeled = FlowGraph::duplicateRegion(irManager, originalInvertedHeader, nodesToPeel, defUses, peeledFreq);
                    assert(peeled->getInDegree() <= 1);
                    // Break cycle and link to original loop.
                    if (peeled->getInDegree() == 1) {
                        fg.replaceEdgeTarget(peeled->getInEdges().front(), header);
                    }
                    // Link duplicated region.
                    fg.replaceEdgeTarget(entryEdge, peeled);
                    if(newTail->findTargetEdge(header) == NULL) {
                        //
                        // An intervening stVar block was added to promote a temp to a var 
                        // in the duplicated block.  The new tail should be the stVar block.
                        //
                        tail =  newTail->getUnconditionalEdge()->getTargetNode();
                        assert(tail != NULL && tail->findTargetEdge(header) != NULL);
                    } else {
                        tail = newTail;
                    }
                    assert(header->getInDegree() == 2);
                    preheader = header->getInEdges().front()->getSourceNode();
                    if(preheader == tail)
                        preheader = header->getInEdges().back()->getSourceNode();            
                }            
            }
            if(preheader->getOutDegree() > 1) {
                Edge* edge = preheader->findTargetEdge(header);
                assert(edge != NULL);
                preheader = fg.spliceBlockOnEdge(edge, instFactory.makeLabel());
            }

        } else {            
            while(isInversionCandidate(header, header, nodesInLoop, next, exit)) {
                if(Log::isEnabled()) {
                    Log::out() << "Consider peeling node at L"; FlowGraph::printLabel(Log::out(), header); Log::out() << std::endl;
                }
                assert(header->isBlockNode());
                assert(header->getInDegree() == 2);            
                assert(header->findSourceEdge(preheader) != NULL);
                assert(header->findSourceEdge(tail) != NULL);
                
                // Find variant instructions.  Invariant instructions need not be duplicated.
                StlVector<Inst*> variantInsts(tmm);
                StlHashSet<Opnd*> variantOpnds(tmm);
                StlVector<Inst*> invariantInsts(tmm);
                Inst* first = (Inst*)header->getFirstInst();
                Inst* inst;
                for(inst = first->getNextInst(); inst != NULL; inst = inst->getNextInst()) {
                    if (isVariantInst(inst, variantOpnds)) {
                        if (Log::isEnabled()) {
                            Log::out() << "Inst ";
                            inst->print(Log::out());
                            Log::out() << " is variant" << std::endl;
                        }
                        variantInsts.push_back(inst);
                        Opnd* dst = inst->getDst();
                        variantOpnds.insert(dst);
                    } else {
                        if (Log::isEnabled()) {
                            Log::out() << "Inst ";
                            inst->print(Log::out());
                            Log::out() << " is invariant" << std::endl;
                        }
                        invariantInsts.push_back(inst);
                    }
                }
                
                // Heuristic #0: If no invariant in header, don't peel.
                if (invariantInsts.empty()) {
                    Log::out() << "Peeling heuristic #0, no invariant" << std::endl;
                    break;
                }
                
                // Heuristic #1: If the last instruction is a variant check, stop peeling.
                Inst* last = (Inst*)header->getLastInst();
                if (last->getOperation().isCheck() && !variantInsts.empty() && last == variantInsts.back() &&
                   !(last->getDst()->isNull() 
                     || (last->getDst()->getType()->tag == Type::Tau))) {
                    hoistHeaderInvariants(preheader, header, invariantInsts);
                    Log::out() << "Peeling heuristic #1, last inst is variant check" << std::endl;
                    break;
                }
                // Heuristic #2: If a defined tmp may be live on exit, don't peel this node.
                // Promoting such tmps to vars is expensive, since we need to find all uses.
                StlVector<Inst*> globalInsts(tmm);
                Opnd* unhandledGlobal = NULL;
                bool hasExit = exit != NULL;
                bool exitIsUnwind = hasExit && (exit == fg.getUnwindNode());
                bool exitIsNotDominated = !hasExit ||
                    (dom.hasDomInfo(header) && dom.hasDomInfo(exit) && !dom.dominates(header, exit));
                StlVector<Inst*>::iterator iiter;
                for(iiter = variantInsts.begin(); iiter != variantInsts.end(); ++iiter) {
                    Inst* inst = *iiter;
                    Opnd* dst = inst->getDst();
                    if (dst->isGlobal() && !dst->isVarOpnd() && !dst->isNull()) {
                        // Defined global temp.
                        if(exitIsNotDominated || exitIsUnwind || (inst == last && exit->isDispatchNode())) {
                            globalInsts.push_back(inst);
                        } else {
                            unhandledGlobal = dst;
                            break;
                        }
                    }
                }
                if (unhandledGlobal != NULL) {
                    if (Log::isEnabled()) {
                        Log::out() << "Stop peeling node at " ; FlowGraph::printLabel(Log::out(), header); Log::out() << ": unhandled global operand. ";
                        unhandledGlobal->print(Log::out());
                        Log::out() << std::endl;
                    }
                    hoistHeaderInvariants(preheader, header, invariantInsts);
                    break;
                }
                
                // Duplicate instructions
                Node* peeled = fg.createBlockNode(instFactory.makeLabel());
                if (Log::isEnabled()) {
                    Log::out() << "Peeling node "; FlowGraph::printLabel(Log::out(), header); Log::out() << " as ";  FlowGraph::printLabel(Log::out(), peeled); Log::out() << std::endl;
                }
                Inst* nextInst;
                // Peel instructions to peeled block.  Leave clones of variant insts.
                for(inst = first->getNextInst(), iiter = variantInsts.begin(); inst != NULL; inst = nextInst) {
                    nextInst = inst->getNextInst();
                    if (iiter != variantInsts.end() && inst == *iiter) {
                        // Make clone in place.
                        ++iiter;
                        Inst* clone = instFactory.clone(inst, opndManager, duplicateTable);
                        clone->insertBefore(nextInst);
                        inst->unlink();
                        if (Log::isEnabled()) {
                            Log::out() << "Peeling: copying ";
                            inst->print(Log::out());
                            Log::out() << " to ";
                            clone->print(Log::out());
                            Log::out() << std::endl;
                        }
                    } else {
                        if(inst->getOperation().canThrow())
                            FlowGraph::eliminateCheck(fg, header, inst, false);
                        else
                            inst->unlink();
                        if (Log::isEnabled()) {
                            Log::out() << "Peeling: not copying ";
                            inst->print(Log::out());
                            Log::out() << std::endl;
                        }
                    }
                    peeled->appendInst(inst);
                }
                assert(iiter == variantInsts.end());
                
                fg.replaceEdgeTarget(preheader->findTargetEdge(header), peeled);
                if (hasExit) {
                    fg.addEdge(peeled, exit);
                }
                fg.addEdge(peeled, next);
                if (!globalInsts.empty()) {
                    OpndRenameTable* patchTable = new (tmm) OpndRenameTable(tmm);
                    
                    // Need to patch global defs.  Create store blocks and merge at next
                    if (Log::isEnabled()) {
                        Log::out() << "Merging global temps in node ";FlowGraph::printLabel(Log::out(), header); Log::out()<<" and ";FlowGraph::printLabel(Log::out(), peeled);Log::out()<<std::endl;
                    }
                    Node* newpreheaderSt = fg.createBlockNode(instFactory.makeLabel());
                    Node* newtailSt = fg.createBlockNode(instFactory.makeLabel());
                    fg.replaceEdgeTarget(peeled->findTargetEdge(next), newpreheaderSt);
                    fg.addEdge(newpreheaderSt, next);
                    fg.replaceEdgeTarget(header->findTargetEdge(next), newtailSt);
                    fg.addEdge(newtailSt, next);
                    
                    StlVector<Inst*>::iterator i;
                    for(i = globalInsts.begin(); i != globalInsts.end(); ++i) {
                        Inst* inst = *i;
                        Opnd* dst = inst->getDst();
                        Opnd* dstPreheader = opndManager.createSsaTmpOpnd(dst->getType());
                        Opnd* dstTail = duplicateTable->getMapping(dst);
                        inst->setDst(dstPreheader);
                        VarOpnd* dstVar;
                        
                        if ((inst->getOpcode() == Op_LdVar) && (variantOpnds.find(inst->getSrc(0)) == variantOpnds.end())) {
                            // If dst is generated from a LdVar, reuse that var instead of promoting to a new var.
                            dstVar = inst->getSrc(0)->asVarOpnd();
                            assert(dstVar != NULL);
                        } else {
                            // Create a new var and initialize it the original and duplicated blocks.
                            dstVar = opndManager.createVarOpnd(dst->getType(), false);
                            Inst* stPreheader = instFactory.makeStVar(dstVar, dstPreheader);
                            newpreheaderSt->appendInst(stPreheader);
                            Inst* stTail = instFactory.makeStVar(dstVar, dstTail);
                            newtailSt->appendInst(stTail);
                        }
                        
                        Inst* ldVar = instFactory.makeLdVar(dst, dstVar);
                        next->prependInst(ldVar);
                        
                        patchTable->setMapping(dst, dstPreheader);
                    }
                    FlowGraph::renameOperandsInNode(peeled, patchTable);
                    
                    // Rotate
                    preheader = newpreheaderSt;
                    tail = newtailSt;
                } else {
                    if (peeled->getOutDegree() > 1) {
                        // Remove critical edge
                        preheader = fg.createBlockNode(instFactory.makeLabel());
                        fg.replaceEdgeTarget(peeled->findTargetEdge(next), preheader);
                        fg.addEdge(preheader, next);
                    } else {
                        preheader = peeled;
                    }
                    tail = header;
                }
                
                // Prepare to peel next node.
                header = next;
                if (flags.aggressive_peeling) {
                    if (header == originalInvertedHeader) {
                        if (Log::isEnabled()) {
                            Log::out()<<"Stop peeling node at ";FlowGraph::printLabel(Log::out(), header); Log::out() << ": peeled one iteration" << std::endl;
                        }
                        break;
                    }
                } else {
                    break;
                }
            }
        }
        assert(header->getInDegree() == 2);
        backEdge = header->findSourceEdge(tail);
        assert(backEdge != NULL);
        *i = backEdge;
    }
    loopEdgesIn.clear();

    if(flags.insideout_peeling) {
        StlVector<Edge*>::reverse_iterator i = loopEdges.rbegin();
        while (i != loopEdges.rend()) {
            loopEdgesIn.insert(loopEdgesIn.end(), *i);
            i++;
        }
    } else {
        StlVector<Edge*>::iterator i = loopEdges.begin();
        while (i != loopEdges.end()) {
            loopEdgesIn.insert(loopEdgesIn.end(), *i);
            i++;
        }
    }
}

class EdgeCoalescerCallbackImpl : public EdgeCoalescerCallback {
friend class LoopBuilder;
public:
    EdgeCoalescerCallbackImpl(IRManager& _irm) : ssaAffected(false), irm(_irm){}
    
    virtual void coalesce(Node* header, Node* newPreHeader, U_32 numEdges) {
        InstFactory& instFactory = irm.getInstFactory();
        OpndManager& opndManager = irm.getOpndManager();
        Inst* labelInst = (Inst*)header->getFirstInst();
        assert(labelInst->isLabel() && !labelInst->isCatchLabel());
        newPreHeader->appendInst(instFactory.makeLabel());
        newPreHeader->getFirstInst()->setBCOffset(labelInst->getBCOffset());
        if (numEdges > 1 ) {
            for (Inst* phi = labelInst->getNextInst();phi!=NULL && phi->isPhi(); phi = phi->getNextInst()) {
                Opnd *orgDst = phi->getDst();
                SsaVarOpnd *ssaOrgDst = orgDst->asSsaVarOpnd();
                assert(ssaOrgDst);
                VarOpnd *theVar = ssaOrgDst->getVar();
                assert(theVar);
                SsaVarOpnd* newDst = opndManager.createSsaVarOpnd(theVar);
                Inst *newInst = instFactory.makePhi(newDst, 0, 0);
                PhiInst *newPhiInst = newInst->asPhiInst();
                assert(newPhiInst);
                U_32 n = phi->getNumSrcOperands();
                for (U_32 i=0; i<n; i++) {
                    instFactory.appendSrc(newPhiInst, phi->getSrc(i));
                }
                PhiInst *phiInst = phi->asPhiInst();
                assert(phiInst);
                instFactory.appendSrc(phiInst, newDst);
                newPreHeader->appendInst(newInst);
                ssaAffected = true;
            }
        }
    }

private:
    bool ssaAffected;
    IRManager& irm;
};

void LoopBuilder::computeLoops(bool normalize) {
    // find all loop headers
    LoopTree* lt = irManager.getLoopTree();
    if (lt == NULL) {
        MemoryManager& mm = irManager.getMemoryManager();
        EdgeCoalescerCallbackImpl* c = new (mm) EdgeCoalescerCallbackImpl(irManager);
        lt = new LoopTree(irManager.getMemoryManager(), &irManager.getFlowGraph(),c);
        irManager.setLoopTree(lt);
    }
    EdgeCoalescerCallbackImpl* callback = (EdgeCoalescerCallbackImpl*)lt->getCoalesceCallback();
    callback->ssaAffected = false;
    lt->rebuild(normalize);
    needsSsaFixup = callback->ssaAffected;
}

void LoopBuilder::peelLoops() {
    LoopTree*lt = irManager.getLoopTree();
    if (!lt->hasLoops())  {
        return;
    }

    MemoryManager tmm("LoopBuilder::peelLoops");
    Edges loopEdges(tmm);
    const Nodes& nodes = irManager.getFlowGraph().getNodes();
    for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) {
        Node* node = *it;
        const Edges& edges = node->getOutEdges();
        for (Edges::const_iterator ite = edges.begin(), ende = edges.end(); ite!=ende; ++ite) {
            Edge* edge = *ite;
            if (lt->isBackEdge(edge)) {
                loopEdges.push_back(edge);
            }
        }
    }
    peelLoops(loopEdges);
    if (Log::isEnabled()) 
        FlowGraph::printHIR(Log::out(), irManager.getFlowGraph(), irManager.getMethodDesc());


    if (needSsaFixup()) {
        OptPass::fixupSsa(irManager);
    }
    OptPass::smoothProfile(irManager);
}
}//namespace Jitrino