/*
*  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, Mikhail Y. Fursov
*/

#include "escapeanalyzer.h"
#include "Log.h"
#include "Inst.h"
#include "Dominator.h"
#include "irmanager.h"
#include "LoopTree.h"
#include "FlowGraph.h"
#include "ssa/SSA.h"
#include "Opnd.h"

namespace Jitrino {

//TODOs:
// 1) support parents loop unrolling -> easy
// 2) support complete loop elimination if limit is const -> easy  (or do not unroll at all)
// 3) support more branch types (Cmp_Eq, Cmp_NotEq, Cmp_Zero..)
// 4) support loop unrolling for counters with long, float and double types

class UnrollFlags {
public:
    UnrollFlags() 
        : smallLoopSize(0), smallLoopHotness(0), smallLoopUnrollCount(0),
        mediumLoopSize(0), mediumLoopHotness(0), mediumLoopUnrollCount(0),
        largeLoopSize(0), largeLoopHotness(0), largeLoopUnrollCount(0)
    {}

    int  smallLoopSize;
    int  smallLoopHotness;
    int  smallLoopUnrollCount;

    int  mediumLoopSize;
    int  mediumLoopHotness;
    int  mediumLoopUnrollCount;

    int  largeLoopSize;
    int  largeLoopHotness;
    int  largeLoopUnrollCount;

    bool unrollParentLoops;
};

class LoopUnrollAction : public Action {
public:
    void init();
    const UnrollFlags& getFlags() {return flags;}
protected:
    UnrollFlags flags;
};

DEFINE_SESSION_ACTION_WITH_ACTION(LoopUnrollPass, LoopUnrollAction, unroll, "Loop Unrolling")


//loop structure is
//loop {
// BodyA
// check
// BodyB
//}
// all paths from bodyA to bodyB must go through the 'check'
//
class LoopUnrollInfo {
public:
    LoopUnrollInfo() 
        : header(NULL), branchInst(NULL), branchTargetIsExit(false),
        branchLimitOpndPos(0), increment(0), unrollCount(0), doUnroll(false) 
    {}

    Node* header;
    BranchInst* branchInst;
    bool  branchTargetIsExit;
    int   branchLimitOpndPos;
    
    int increment; 
    int unrollCount;
    bool   doUnroll;

    
    Opnd* getLimitOpnd() const {return branchLimitOpndPos==0?branchInst->getSrc(0) : branchInst->getSrc(1);}
    Opnd* getIdxOpnd() const {return branchLimitOpndPos==0?branchInst->getSrc(1) : branchInst->getSrc(0);}
    
    void print(std::ostream& out) const {
        out<<"LoopHead=";FlowGraph::printLabel(out, header);
        out<<" inst=I"<<branchInst->getId();
        out<<" idx-opndId="<<getIdxOpnd()->getId();
        out<<" limit-opndId="<<getLimitOpnd()->getId();
        out<<" increment="<<increment;
        out<<" unroll_count="<<unrollCount;
        out<<" do_unroll="<<doUnroll;
    }
};

class OpndLoopInfo {
public:
    enum OpndType {DEF_OUT_OF_LOOP, LD_CONST, COUNTER, UNDEF};
    OpndLoopInfo() {type=DEF_OUT_OF_LOOP; val=0; phiSplit= false;}

    OpndType getType() const {return type;}
    void setType(OpndType newType) {assert(type!=newType);type = newType; val=0;}
    bool isCounter() const {return type == COUNTER;}
    bool isLDConst() const {return type == LD_CONST;}
    bool isDOL() const {return type == DEF_OUT_OF_LOOP;}
    bool isUndefined() const {return type == UNDEF;}
    int getConst() const {assert(getType()==LD_CONST); return val;}
    void setConst(I_32 v) {assert(getType()==LD_CONST); val=v;}
    int getIncrement() const {assert(getType()==COUNTER); return val;}
    void setIncrement(I_32 v) {assert(getType()==COUNTER); val=v;}
    bool isPhiSplit() const {return phiSplit;}
    void markPhiSplit() {assert(isCounter()); phiSplit = true;}
    
    
    void print(std::ostream& out) {
        if (type == DEF_OUT_OF_LOOP) out << "DOL"; 
        else if (type == LD_CONST)   out << "LDC:"<<getConst();
        else if (type == COUNTER)    out << "CNT:"<<getIncrement() << (phiSplit?" splt":"");
        else                         out << "UNDEF";
    }
private:
    OpndType type;
    int      val;
    bool     phiSplit; //only 1 phi split with DOL is allowed for counters.
};

typedef StlVector<Inst*> InstStack;
typedef StlVector<LoopUnrollInfo*> UnrollInfos;

static void log_ident(size_t n)  {for (size_t i=0;i<n;++i) Log::out()<<"  "; }
static int signof(int v) { return (v == 0) ? 0 : ( v < 0 ? -1 : 1); }


static void findLoopsToUnroll(MemoryManager& mm, IRManager& irm, UnrollInfos& result, const UnrollFlags& flags);
static void doUnroll(MemoryManager& mm, IRManager& irm, const LoopUnrollInfo* info, const UnrollFlags& flags);
static void calculateReachableNodesInLoop(LoopNode* loop, Node* node, Node* stopNode, BitSet& flags);


void LoopUnrollAction::init() {
    flags.smallLoopSize = getIntArg("small_loop_max_size", 5);
    flags.smallLoopHotness = getIntArg("small_loop_hotness_percent", 300);
    flags.smallLoopUnrollCount = getIntArg("small_loop_unroll_count", 8);

    flags.mediumLoopSize = getIntArg("medium_loop_max_size", 10);
    flags.mediumLoopHotness = getIntArg("medium_loop_hotness_percent", 300);
    flags.mediumLoopUnrollCount = getIntArg("medium_loop_unroll_count", 4);

    flags.largeLoopSize = getIntArg("large_loop_max_size", 20);
    flags.largeLoopHotness = getIntArg("large_loop_hotness_percent", 300);
    flags.largeLoopUnrollCount = getIntArg("large_loop_unroll_count", 2);

//TODO: support unrolling of parent loops
    flags.unrollParentLoops = false;//getBoolArg("unroll_parent_loops", false);
}

void LoopUnrollPass::_run(IRManager& irm) {
    const UnrollFlags& flags = ((LoopUnrollAction*)getAction())->getFlags();
    
    OptPass::computeDominatorsAndLoops(irm);
    ControlFlowGraph& cfg = irm.getFlowGraph();
    LoopTree* lt = cfg.getLoopTree();
    if (!lt->hasLoops()) {
        return;
    }
    
    MemoryManager mm("loopUnrollMM");
    UnrollInfos loopsToUnroll(mm);
    findLoopsToUnroll(mm, irm, loopsToUnroll, flags);
    if (loopsToUnroll.empty()) {
        if (Log::isEnabled()) Log::out() << "No candidates found to unroll"<<std::endl;
        return;
    }
    if (Log::isEnabled()) {
        Log::out()<<"Loops to unroll before filtering:"<<std::endl;
        for (UnrollInfos::const_iterator it = loopsToUnroll.begin(), end = loopsToUnroll.end();it!=end; ++it) {
            const LoopUnrollInfo* info = *it;
            info->print(Log::out()); Log::out()<<std::endl;
        }
    }
    bool hasProfile =  cfg.hasEdgeProfile();
    //filter out that can't be unrolled, calculate BodyA and BodyB
    BitSet bodyANodes(mm, cfg.getMaxNodeId()), bodyBNodes(mm, cfg.getMaxNodeId());
    for (UnrollInfos::iterator it = loopsToUnroll.begin(), end = loopsToUnroll.end();it!=end; ++it) {
        LoopUnrollInfo* info = *it;
        if (info == NULL) {
            continue;
        }
        if (!info->doUnroll) {
            *it=NULL;
            continue;
        }
        Node* header=info->header;
        LoopNode* loopHeader = lt->getLoopNode(header, false);
        assert(loopHeader->getHeader() == header);

        Node* checkNode = info->branchInst->getNode();
        bodyANodes.clear();
        bodyBNodes.clear();
        calculateReachableNodesInLoop(loopHeader, loopHeader->getHeader(), checkNode, bodyANodes);
        calculateReachableNodesInLoop(loopHeader, checkNode, NULL, bodyBNodes);
        bodyANodes.intersectWith(bodyBNodes);
        bool checkNodeIsJunctionPoint = bodyANodes.isEmpty();
        if (!checkNodeIsJunctionPoint) {
            if (Log::isEnabled()) {
                Log::out()<<"Check node is not a junction point -> removing from the list: branch inst id=I"<<info->branchInst->getId()<<std::endl;
            }
            *it=NULL;
            continue;
        }
        //check if branch semantic is OK
        ComparisonModifier cmpMod = info->branchInst->getModifier().getComparisonModifier();
        if (cmpMod!=Cmp_GT && cmpMod!=Cmp_GTE && cmpMod!=Cmp_GT_Un && cmpMod!=Cmp_GTE_Un) {
            if (Log::isEnabled()) {
                Log::out()<<"Branch is not a range comparison -> removing from the list: branch inst id=I"<<info->branchInst->getId()<<std::endl;
            }
            *it=NULL;
            continue;
        }

        //check config settings
        bool failed = false;
        int nodesInLoop = (int)loopHeader->getNodesInLoop().size();
        const char* reason = "unknown";
        if (nodesInLoop > flags.largeLoopSize) {
            reason = "loop is too large";
            failed = true;
        } else if (hasProfile) {
            int headHotness = (int)(header->getExecCount()*100.0  / cfg.getEntryNode()->getExecCount());
            int minHeaderHotness= nodesInLoop <= flags.smallLoopSize ? flags.smallLoopHotness :
                nodesInLoop <= flags.mediumLoopSize ? flags.mediumLoopHotness : flags.largeLoopHotness;
            info->unrollCount = nodesInLoop <= flags.smallLoopSize ? flags.smallLoopUnrollCount :
                nodesInLoop <= flags.mediumLoopSize? flags.mediumLoopUnrollCount: flags.largeLoopUnrollCount;
            failed = headHotness < minHeaderHotness || info->unrollCount < 1;
            if (failed) {
                reason = "loop is too cold";
            }
        }
        if (failed) {
            if (Log::isEnabled()) {
                Log::out()<<"Loop does not match unroll configuration ("<<reason<<") -> removing from the list: branch inst id=I"<<info->branchInst->getId()<<std::endl;
            }
            *it=NULL;
        }
    }    
    //filter out loops with multiple exits 
    for (UnrollInfos::iterator it1 = loopsToUnroll.begin(), end = loopsToUnroll.end();it1!=end; ++it1) {
        const LoopUnrollInfo* info1 = *it1;
        if (info1== NULL) {
            continue;
        }
        Node* header=info1->header;
        for (UnrollInfos::iterator it2 = it1+1; it2!=end; ++it2) {
            const LoopUnrollInfo* info2 = *it2;
            if (info2!=NULL && header==info2->header) {
                if (Log::isEnabled()) {
                    Log::out() << "Found multiple exits:"; FlowGraph::printLabel(Log::out(), header);Log::out()<<std::endl;
                }
                if (hasProfile)  {
                    Node* check1 = info1->branchInst->getNode();
                    Node* check2 = info2->branchInst->getNode();
                    if (check1->getExecCount() > check2->getExecCount()) {
                        *it2 = NULL;
                    } else {
                        *it1 = NULL;
                    }
                } else { // random selection
                    *it2=NULL;
                }
            }
        }
    }    
    loopsToUnroll.erase(std::remove(loopsToUnroll.begin(), loopsToUnroll.end(), (LoopUnrollInfo*)NULL), loopsToUnroll.end());
    if (loopsToUnroll.empty()) {
        if (Log::isEnabled()) Log::out() << "--------No candidates to unroll left after filtering"<<std::endl;
        return;
    }
    
    //dessa CFG before unrolling -> need to duplicate regions and we can do it on dessa form only today
    {
        SSABuilder::deconvertSSA(&cfg, irm.getOpndManager());
        irm.setInSsa(false);
    }

    if (Log::isEnabled()) {
        Log::out()<<"--------Loops to unroll after filtering : n="<<loopsToUnroll.size()<<std::endl;
            for (UnrollInfos::const_iterator it = loopsToUnroll.begin(), end = loopsToUnroll.end();it!=end; ++it) {
                const LoopUnrollInfo* info = *it;
                info->print(Log::out()); Log::out()<<std::endl;
            }
    }

    for (UnrollInfos::const_iterator it = loopsToUnroll.begin(), end = loopsToUnroll.end();it!=end; ++it) {
        const LoopUnrollInfo* info = *it;
        doUnroll(mm, irm, info, flags);
    }
};

static void calculateReachableNodesInLoop(LoopNode* loop, Node* node, Node* stopNode, BitSet& flags) {
    int id = node->getId();
    if (!loop->inLoop(node) || node == stopNode || flags.getBit(id)) {
        return;
    }
    flags.setBit(id, true);
    const Edges& edges = node->getOutEdges();
    for (Edges::const_iterator ite = edges.begin(), ende = edges.end(); ite!=ende; ++ite) {
        Edge* e = *ite;
        Node* nextNode = e->getTargetNode();
        if (nextNode != loop->getHeader()) {
            calculateReachableNodesInLoop(loop, nextNode, stopNode, flags);
        }
    }
}


static OpndLoopInfo processOpnd(LoopNode* loopHead, LoopTree* lt, InstStack& defStack, Opnd* opnd) {
    OpndLoopInfo result;
    Inst* defInst = opnd->getInst();
    if (Log::isEnabled()) {
        log_ident(defStack.size()); defInst->print(Log::out()); Log::out()<<"]"<<std::endl;
    }
    if (std::find(defStack.begin(), defStack.end(), defInst)!=defStack.end()) {
        result.setType(OpndLoopInfo::COUNTER);
        result.setIncrement(0);
        if (Log::isEnabled()) {
            log_ident(defStack.size()); 
            Log::out()<<"Found duplicate in def stack -> stopping recursion. ";result.print(Log::out()); Log::out()<<std::endl;
        }
        return result;
    }
    Node* defNode = defInst->getNode();
    Opcode opcode = defInst->getOpcode();

    if (opcode == Op_LdConstant) {
        result.setType(OpndLoopInfo::LD_CONST);
        result.setConst(defInst->asConstInst()->getValue().i4);
        if (Log::isEnabled()) {
            log_ident(defStack.size()); 
            Log::out()<<"assigning to const -> stopping recursion. ";result.print(Log::out());Log::out()<<std::endl;
        }
        return result;
    }
    if (!loopHead->inLoop(defNode)) {
        if (Log::isEnabled()) {
            log_ident(defStack.size());
            Log::out()<<"Inst out of the loop -> stopping recursion. ";result.print(Log::out()); Log::out()<<std::endl;
        }
        return result;
    }

    defStack.push_back(defInst);
    if (opcode == Op_Phi) {
        OpndLoopInfo info1 = processOpnd(loopHead, lt, defStack, defInst->getSrc(0));
        OpndLoopInfo info2 = processOpnd(loopHead, lt, defStack, defInst->getSrc(1));
        if (Log::isEnabled()) {
            log_ident(defStack.size());
            Log::out()<<"PHI(";info1.print(Log::out());Log::out()<<",";info2.print(Log::out());Log::out()<<")"<<std::endl;
        }
        if ( ((info1.isCounter() && !info1.isPhiSplit()) && (info2.isDOL() || info2.isLDConst()))
             || ((info2.isCounter() && !info2.isPhiSplit()) && (info1.isDOL() || info1.isLDConst())) )
        {
            result.setType(OpndLoopInfo::COUNTER);
            result.setIncrement(info1.isCounter() ? info1.getIncrement() : info2.getIncrement());
            result.markPhiSplit();
        } else {
            result.setType(OpndLoopInfo::UNDEF);
        }
    } else if (opcode == Op_Add || opcode == Op_Sub) { //todo: LADD 
        Opnd *op1 = defInst->getSrc(0);
        Opnd *op2 = defInst->getSrc(1);
        OpndLoopInfo info1 = processOpnd(loopHead, lt, defStack, op1);
        OpndLoopInfo info2 = processOpnd(loopHead, lt, defStack, op2);
        if ((info1.isLDConst() || info1.isDOL()) && (info2.isLDConst() || info2.isDOL())) {
            if (info1.isLDConst() && info2.isLDConst() && info1.getConst() == info2.getConst()) {
                result.setType(OpndLoopInfo::LD_CONST);
                result.setConst(info1.getConst());
            } else {
                //result is DOL (default type)
            }
        } else if ((info1.isCounter() && info2.isLDConst()) || (info2.isCounter() && info1.isLDConst())) {
            int increment = info1.isCounter()? info1.getIncrement(): info2.getIncrement();
            int diff = info1.isLDConst()? info1.getConst(): info2.getConst(); 

            //we use SSA form to analyze how opnd changes in loop and we do not analyze actual control flow, 
            // so we can unroll loops with monotonically changing 'counters' only.
            //Example: when 'counter' changes not monotonically and we can't unroll:
            //idx=0; loop {idx+=100; if(idx>=100) break; idx-=99;} ->'increment'=1 but not monotonicaly.
            bool monotonousFlag = increment == 0 || diff == 0 
                || (opcode == Op_Add && signof(diff) == signof(increment)) 
                || (opcode == Op_Sub && signof(diff) != signof(increment));
            if (monotonousFlag) {
                result.setType(OpndLoopInfo::COUNTER);
                if ((info1.isCounter() && info1.isPhiSplit()) || (info2.isCounter() && info2.isPhiSplit())) {
                    result.markPhiSplit();
                }
                //TO IMPROVE: for loops like: for (; length-1>=0;length--){...}
                //we have 2 SUBs by -1 => "-2", but real counter is changed by "-1".
                //Loop unroll will use "-2". It's ok, because this value is used in a guard inst
                //and ABS(increment_in_unroll) >= ABS(real_increment). This work only for monotonous loops.
                //To make increment_in_unroll == real_increment we must track modifications (SUB,ADD) that affects vars only.
                if (opcode == Op_Add) {
                    result.setIncrement(increment + diff);
                } else {
                    result.setIncrement(increment - diff);
                }
            } else {
                result.setType(OpndLoopInfo::UNDEF);
            }
        } else {
            result.setType(OpndLoopInfo::UNDEF);
        }
    } else if (opcode == Op_StVar  || opcode == Op_LdVar) {
        Opnd* newOpnd = defInst->getSrc(0);
        result  = processOpnd(loopHead, lt, defStack, newOpnd);
    } else if (opcode == Op_TauArrayLen) {
        Opnd* arrayOpnd  = defInst->getSrc(0);
        result  = processOpnd(loopHead, lt, defStack, arrayOpnd);
    } else { //unsupported op
        result.setType(OpndLoopInfo::UNDEF);
        if (Log::isEnabled()) {
            log_ident(defStack.size()); Log::out()<<"unknown op -> stopping recursion. ";
        }
    }
    defStack.pop_back();
    if (Log::isEnabled()) {
        log_ident(defStack.size());
        result.print(Log::out());Log::out()<<std::endl;
    }
    return result;
}

static LoopUnrollInfo* prepareUnrollInfo(MemoryManager& mm, LoopTree* lt, BranchInst* branchInst) {

    if (Log::isEnabled()) {
        Log::out()<<"==Checking loop exit:"; branchInst->print(Log::out()); Log::out()<<std::endl;
    }

    //traverse loop and track all modifications
    Node* node = branchInst->getNode();
    LoopNode* loopHeader = lt->getLoopNode(node, false);
    Opnd* opnd1 = branchInst->getSrc(0);
    Opnd* opnd2 = branchInst->getNumSrcOperands()==1?NULL:branchInst->getSrc(1);
    
    if (opnd2==NULL) {
        assert(branchInst->getComparisonModifier() == Cmp_Zero || branchInst->getComparisonModifier() == Cmp_NonZero);
        assert(opnd1->getType()->isObject());
        if (Log::isEnabled()) {
            Log::out()<<"----Unsupported comparison modifier."<<std::endl;
        }
        return NULL;
    }
    
    if (!opnd1->getType()->isInteger() || opnd1->getType()->isInt8()
        || !opnd2->getType()->isInteger() || opnd2->getType()->isInt8()) 
    {
        if (Log::isEnabled()) {
            Log::out()<<"----Unsupported opnd types."<<std::endl;
        }
        return NULL;        //IMPROVE: longs and floating types are not supported
    }

    InstStack defStack(mm);

    Log::out()<<"----Analyzing opnd1 id="<<opnd1->getId()<<std::endl;
    OpndLoopInfo opndInfo1 = processOpnd(loopHeader, lt, defStack, opnd1);
    assert(defStack.empty());
    
    Log::out()<<"----Analyzing opnd2 id="<<opnd2->getId()<<std::endl;
    OpndLoopInfo opndInfo2 = processOpnd(loopHeader, lt, defStack, opnd2);
    assert(defStack.empty());

    if(Log::isEnabled()) {
        Log::out()<<"----Result: opndId1="<<opnd1->getId()<<" type=";opndInfo1.print(Log::out());
        Log::out()<<", opndId2="<<opnd2->getId()<<" type=";opndInfo2.print(Log::out());Log::out()<<std::endl;
    }

    //default values -> this item will not be unrolled unless all constraints are OK
    LoopUnrollInfo* info = new (mm) LoopUnrollInfo();
    info->header = loopHeader->getHeader();
    info->branchInst = branchInst;
    info->branchTargetIsExit = !loopHeader->inLoop(branchInst->getTargetLabel()->getNode());
    info->doUnroll = false;

    if (opndInfo1.isCounter() && (opndInfo2.isDOL() || opndInfo2.isLDConst())) {
        info->doUnroll = true;
        info->branchLimitOpndPos=1;
        info->increment = opndInfo1.getIncrement();
    } else  if (opndInfo2.isCounter() && (opndInfo1.isDOL() || opndInfo1.isLDConst())) {
        info->doUnroll = true;
        info->branchLimitOpndPos=0;
        info->increment = opndInfo2.getIncrement();
    } 
    return info;
}

void findLoopsToUnroll(MemoryManager& tmpMM, IRManager& irm, UnrollInfos& result, const UnrollFlags& flags) {

    ControlFlowGraph& fg = irm.getFlowGraph();
    LoopTree* lt = fg.getLoopTree();

    //find all loop exits
    Edges loopExits(tmpMM);
    const Nodes& nodes = fg.getNodes();
    for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) {
       Node* node = *it;
        LoopNode* loopNode = lt->getLoopNode(node, false);
        if (loopNode == NULL) {
            continue; //node not in a loop
        }
        if (!flags.unrollParentLoops && loopNode->getChild()!=NULL) {
            continue; //skip parent loops
        }
        const Edges& edges = node->getOutEdges();
        for (Edges::const_iterator ite = edges.begin(), ende = edges.end(); ite!=ende; ++ite) {
           Edge* edge = *ite;
            if (lt->isLoopExit(edge)) {
                loopExits.push_back(edge);
            }
        }
    }
   
    //filter out all edges except branches
    for (Edges::iterator ite = loopExits.begin(), ende = loopExits.end(); ite!=ende; ++ite) {
       Edge* edge = *ite;
        if (edge->isDispatchEdge() || edge->isUnconditionalEdge() || edge->isCatchEdge()) {
            *ite = NULL;
            continue;
        }
        Inst* lastInst = (Inst*)edge->getSourceNode()->getLastInst();
        if (lastInst->isSwitch()) {
            *ite = NULL;
            continue;
        }
        assert(lastInst->isBranch());
        assert(edge->isFalseEdge() || edge->isTrueEdge());
    }
    loopExits.erase(std::remove(loopExits.begin(), loopExits.end(), (Edge*)NULL), loopExits.end());

    // analyze every loop exit and prepare unroll info
    for (Edges::const_iterator ite = loopExits.begin(), ende = loopExits.end(); ite!=ende; ++ite) {
        Edge* edge = *ite;
        Node* sourceNode = edge->getSourceNode();
        Inst* lastInst = (Inst*)sourceNode->getLastInst();
        assert(lastInst->isBranch());
        LoopUnrollInfo* info = prepareUnrollInfo(tmpMM, lt, lastInst->asBranchInst());
        if (info == NULL) {
            continue;
        }
        if (Log::isEnabled()) {
            info->print(Log::out());
            Log::out()<<std::endl;
        }
        result.push_back(info);
    }
}

static void doUnroll(MemoryManager& mm, IRManager& irm, const LoopUnrollInfo* info, const UnrollFlags& flags) {
    //unroll algorithm does the following
    //before:
    // loopOrig {
    //    bodyA
    //    check(idxOpnd,limitOpnd)
    //    bodyB
    // }
    //after:
    // unrolledIncOpnd = unrollCount * idx->increment
    // unrolledLimitOpnd = limitOpnd-unrolledIncOpnd;
    // bodyA 
    // loopUnrolled {
    //     check(idxOpnd,unrolledLimitOpnd)
    //     bodyB
    //     bodyA
    //     bodyB
    //     ...
    //     bodyA
    // }
    // loopEpilogue {
    //    check(idxOpnd,limitOpnd)
    //    bodyB
    //    bodyA
    // }
    //
    //where:
    // bodyA - all nodes of the same loop accessible from checkNode via incoming edges
    // bodyB - all nodes except bodyA and checkNode

    ControlFlowGraph& cfg = irm.getFlowGraph();
    LoopTree* lt = cfg.getLoopTree();
    InstFactory& instFactory = irm.getInstFactory();
    OpndManager& opndManager = irm.getOpndManager();
    Type* opType = info->getLimitOpnd()->getType();
    
 //   printf("UNROLL\n");

    //STEP 0: cache all data needed
    assert(info->unrollCount >= 1);
    Node* origHeader = info->header;
    assert(origHeader->getInDegree() == 2); //loop is normalized

    OptPass::computeLoops(irm);//recompute loop info if needed
    LoopNode* loopNode = lt->getLoopNode(origHeader, false); 
    
    Edge* entryEdge = origHeader->getInEdges().front();
    if (lt->isBackEdge(entryEdge)) {
        entryEdge = origHeader->getInEdges().back();
    }
    Node* origCheckNode = info->branchInst->getNode();
    Edge* origLoopExitEdge = info->branchTargetIsExit ? origCheckNode->getTrueEdge() : origCheckNode->getFalseEdge();
    
    U_32 maxNodeId = cfg.getMaxNodeId()+1; //+1 for a split check node
    StlBitVector nodesInLoop(mm, maxNodeId);
    {
        const Nodes& loopNodes = loopNode->getNodesInLoop();
        for (Nodes::const_iterator it = loopNodes.begin(), end = loopNodes.end(); it!=end; ++it) {
            Node* node = *it;
            nodesInLoop.setBit(node->getId());
        }
    }
    
    
    //STEP 1: calculate bodyA nodes
    BitSet aFlags(mm, maxNodeId);
    calculateReachableNodesInLoop(loopNode, origHeader, origCheckNode, aFlags);
    StlBitVector bodyANodes(mm, maxNodeId);
    for (U_32 i=0;i<maxNodeId;i++) bodyANodes.setBit(i, aFlags.getBit(i));
    
    //STEP 2: make checkNode a separate node, prepare loop region
    bodyANodes.setBit(origCheckNode->getId(), true);
    Node* checkNode = cfg.splitNodeAtInstruction(info->branchInst->prev(), true, false, instFactory.makeLabel());
    nodesInLoop.setBit(checkNode->getId(), true);
    Node* preCheckNode = origCheckNode;
    bodyANodes.setBit(preCheckNode->getId(), true);
    
    //STEP 3: rotate original loop
    // before: {bodyA1, check , bodyB}
    // after:  bodyA2 {check, bodyB, bodyA1}
    Edge* bodyA2ToCheckEdge = NULL;
    Opnd* limitOpndInBodyA2 = NULL;
    {
        //WARN: info->limitOpnd and info->indexOpnd can be replaced after code duplication if promoted to vars
        Opnd* limitOpndBefore = info->getLimitOpnd();

        assert(preCheckNode->getOutDegree()==1 && preCheckNode->getUnconditionalEdgeTarget() == checkNode);
        DefUseBuilder defUses(mm);
        defUses.initialize(cfg);
        OpndRenameTable opndRenameTable(mm, maxNodeId); //todo: maxNodeId is overkill estimate here
        NodeRenameTable nodeRenameTable(mm, maxNodeId);
        Node* bodyA2 = FlowGraph::duplicateRegion(irm, origHeader, bodyANodes, defUses, nodeRenameTable, opndRenameTable);
        cfg.replaceEdgeTarget(entryEdge, bodyA2, true);
        
        // while duplicating a region new nodes could be created and 'nodesInRegion' bitvector param is updated. 
        // BodyA is part of the loop -> if new nodes were created in the loop we must track them.
        nodesInLoop.resize(bodyANodes.size());
        for (U_32 i=0;i<bodyANodes.size();i++) nodesInLoop.setBit(i, bodyANodes.getBit(i) || nodesInLoop.getBit(i));

        Node* bodyA2PreCheckNode = nodeRenameTable.getMapping(preCheckNode);
        assert(bodyA2PreCheckNode->getOutDegree()==1 && bodyA2PreCheckNode->getUnconditionalEdgeTarget() == checkNode);
        bodyA2ToCheckEdge = bodyA2PreCheckNode->getUnconditionalEdge();
        limitOpndInBodyA2 = limitOpndBefore;
        if (nodeRenameTable.getMapping(limitOpndBefore->getInst()->getNode())!=NULL) {
            limitOpndInBodyA2 = opndRenameTable.getMapping(limitOpndBefore);
        }
        assert(limitOpndInBodyA2!=NULL);
    }

    //STEP 4: prepare epilogue loop: {check, bodyB, bodyA}
    Node* epilogueLoopHead = NULL;
    {
        DefUseBuilder defUses(mm);
        defUses.initialize(cfg);
        OpndRenameTable opndRenameTable(mm, maxNodeId); //todo: maxNodeId is overkill estimate here
        NodeRenameTable nodeRenameTable(mm, maxNodeId);
        epilogueLoopHead = FlowGraph::duplicateRegion(irm, checkNode, nodesInLoop, defUses, nodeRenameTable, opndRenameTable);
        cfg.replaceEdgeTarget(origLoopExitEdge, epilogueLoopHead, true);
    }

    //STEP 5: prepare unrolledLimitOpnd and replace it in original loop's check
    {
        Node* unrolledPreheader = cfg.spliceBlockOnEdge(bodyA2ToCheckEdge, instFactory.makeLabel());
        Opnd* unrolledIncOpnd = opndManager.createSsaTmpOpnd(opType);
        unrolledPreheader->appendInst(instFactory.makeLdConst(unrolledIncOpnd, info->increment * info->unrollCount));
        Opnd* unrolledLimitOpnd = opndManager.createSsaTmpOpnd(opType);
        Modifier mod = Modifier(SignedOp)|Modifier(Strict_No)|Modifier(Overflow_None)|Modifier(Exception_Never);
        unrolledPreheader->appendInst(instFactory.makeSub(mod, unrolledLimitOpnd, limitOpndInBodyA2, unrolledIncOpnd));
        info->branchInst->setSrc(info->branchLimitOpndPos, unrolledLimitOpnd);
    }

    DefUseBuilder defUses(mm);
    defUses.initialize(cfg);
    //STEP 6: unroll original loop and remove all checks in duplicated bodies
    {
        Edge* backedge = preCheckNode->getUnconditionalEdge();
        for (int i=1;i<info->unrollCount;i++) {
            OpndRenameTable opndRenameTable(mm, maxNodeId);
            NodeRenameTable nodeRenameTable(mm, maxNodeId);

            Node* unrolledRegionHeader = FlowGraph::duplicateRegion(irm, checkNode, nodesInLoop, defUses, nodeRenameTable, opndRenameTable);
            cfg.replaceEdgeTarget(backedge, unrolledRegionHeader, true); 

            Node* newTail = nodeRenameTable.getMapping(preCheckNode);
            assert(newTail->getOutDegree()==1 );
            backedge = newTail->getUnconditionalEdge();
            cfg.replaceEdgeTarget(backedge, checkNode, true);
            
            //remove check from duplicated code
            Node* duplicateCheckNode = nodeRenameTable.getMapping(checkNode);
            assert(duplicateCheckNode->getOutDegree()==2);
            Edge* exitEdge = info->branchTargetIsExit ? duplicateCheckNode->getTrueEdge() : duplicateCheckNode->getFalseEdge();
            duplicateCheckNode->getLastInst()->unlink();
            cfg.removeEdge(exitEdge);
        }
    }
    
    //STEP 7: make old loop colder
    if (cfg.hasEdgeProfile()) {
        Edge* epilogueExit = info->branchTargetIsExit ? epilogueLoopHead->getTrueEdge() : epilogueLoopHead->getFalseEdge();
        epilogueExit->setEdgeProb(epilogueExit->getEdgeProb() * 5);
    }
}   


}//namespace