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

/**
* @author Jack Liu, Mikhail Y. Fursov, Chen-Dong Yuan
*/

#include "EMInterface.h"
#include "Jitrino.h"
#include "Inst.h"
#include "Stl.h"
#include "StaticProfiler.h"
#include "Dominator.h"
#include "Loop.h"
#include "FlowGraph.h"

#include <string.h>
#include <stdio.h>
#include <limits.h>
#include <sstream>

namespace Jitrino {

#define MAX(a, b) ((a)>(b)?a:b)

static bool isMethodTrivial( ControlFlowGraph& cfg );
static void checkBCMapping( ControlFlowGraph& cfg );
static U_32 computeCheckSum( MemoryManager& mm, IRManager& irm, const StlSet<Node*>& nodesToIgnore, bool bcLevel);
static bool calculateProbsFromProfile(MemoryManager& mm, ControlFlowGraph& fg, const Edges& edges, DominatorTree* dt, LoopTree* lt, EdgeMethodProfile* profile, bool bcLevelProfiling, const StlSet<Node*>& nodesToIgnore);
static Node* selectNodeToInstrument(IRManager& irm, Edge* edge);
static void selectEdgesToInstrument(MemoryManager& mm, IRManager& irm, Edges& result, const StlSet<Node*>& nodesToIgnore, bool bcLevel);
static U_32 genKey( U_32 n, Edge* edge, bool bcLevel, bool debug);
static bool hasCatch( Node* node );
static void selectNodesToIgnore(IRManager& irm, LoopTree* lt, StlSet<Node*>& result, bool bcLevel);

class EdgeProfileFlags {
public:
    bool bcLevelProfiling;

    EdgeProfileFlags() : bcLevelProfiling(false) {}
};

class EdgeProfilerAction : public Action {
public:
    void init() {
        flags.bcLevelProfiling = getBoolArg("bcLevel", false);
    }
    const EdgeProfileFlags& getFlags() {return flags;}
protected:
    EdgeProfileFlags flags;
};


DEFINE_SESSION_ACTION_WITH_ACTION(EdgeProfilerInstrumentationPass, EdgeProfilerAction, edge_instrument, "Perform edge instrumentation pass")

void EdgeProfilerInstrumentationPass::_run(IRManager& irm)
{
    ControlFlowGraph& flowGraph = irm.getFlowGraph();
    MemoryManager mm("Edge InstrumentationPass");
    MethodDesc& md = irm.getMethodDesc();
    InstFactory& instFactory = irm.getInstFactory();
    EdgeProfilerAction* action = (EdgeProfilerAction*)getAction();
    const EdgeProfileFlags& flags = action->getFlags();

    bool debug = Log::isEnabled();
    
    if (debug) {
        Log::out()<<"EdgeProfilerInstrumentationPass. BcLevel="<<flags.bcLevelProfiling<<std::endl;
    }

    if (flags.bcLevelProfiling) {
        checkBCMapping(flowGraph);
    }

    OptPass::computeDominatorsAndLoops(irm);
   
    LogStream& irdump = log(LogStream::IRDUMP);
    if (irdump.isEnabled()) {
        printHIR(irm, "IR before instrumentation");
    }

    LoopTree* lt = irm.getLoopTree();    
    //set of nodes with out-edges are not taken into account during instrumentation
    //and checksum calculation
    //such nodes are optional in CFG. E.g. nodes with class initializers insts
    StlSet<Node*> nodesToIgnore(mm);
    selectNodesToIgnore(irm, lt, nodesToIgnore, flags.bcLevelProfiling);
    //compute checksum first
    U_32 _checkSum = computeCheckSum(mm, irm, nodesToIgnore, flags.bcLevelProfiling);
    StlVector<U_32> counterKeys(mm);
    // Instrument method entry first.
    Node* entryNode = flowGraph.getEntryNode();
    entryNode->prependInst(instFactory.makeIncCounter(0));
    bool methodIsTrivial = isMethodTrivial(flowGraph);
    if (!methodIsTrivial) {
        // Scan the CFG node in topological order and record the blocks and
        // edges where we need to add instrumentation code.
        // The actual instrumentation will be done in a separate phase so that
        // we won't disturb the CFG as we are traversing it.
        
        Edges edgesToInstrument(mm);
        selectEdgesToInstrument(mm, irm, edgesToInstrument, nodesToIgnore, flags.bcLevelProfiling);
        //compute edge-ids before CFG modification: edge-ids are part of CFG consistency check.
        for (Edges::const_iterator it = edgesToInstrument.begin(), end = edgesToInstrument.end(); it!=end; ++it) {
            Edge* edge = *it;
            U_32 key = genKey((U_32)counterKeys.size() + 1, edge, flags.bcLevelProfiling, debug);
            assert( key != 0 );
            counterKeys.push_back(key);
        }
        // Now revisit all of the edges that need to be instrumented
        // and generate instrumentation code.
        U_32 i = 0;
        for (Edges::const_iterator it = edgesToInstrument.begin(), end = edgesToInstrument.end(); it!=end; ++it, ++i) {
            Edge* edge = *it;
            Node* nodeToInstrument = selectNodeToInstrument(irm, edge);
            assert(nodeToInstrument!=NULL && nodeToInstrument->isBlockNode());
            U_32 key = counterKeys[i];
            Inst* incInst = instFactory.makeIncCounter( key );
            assert(((Inst*)nodeToInstrument->getFirstInst())->getOpcode() != Op_IncCounter );
            nodeToInstrument->prependInst(incInst);
        }

        if (flags.bcLevelProfiling) { //remove duplicates from keys
            std::sort(counterKeys.begin(), counterKeys.end());
            counterKeys.resize(std::unique(counterKeys.begin(), counterKeys.end()) - counterKeys.begin());
        }
    } 
    
    irm.getCompilationInterface().lockMethodData();
    
    ProfilingInterface* pi = irm.getProfilingInterface();
    if (!pi->hasMethodProfile(ProfileType_Edge, md, JITProfilingRole_GEN)) {
        pi->createEdgeMethodProfile(mm , md,  (U_32)counterKeys.size(),  counterKeys.empty()?NULL:(U_32*)&counterKeys.front(), _checkSum);
    }

    irm.getCompilationInterface().unlockMethodData();

    if (debug) {
        Log::out() << std::endl << "EdgePC:: instrumented, nCounters="<<counterKeys.size() <<" checksum="<<_checkSum << std::endl;
    }

}

DEFINE_SESSION_ACTION_WITH_ACTION(EdgeProfilerAnnotationPass, EdgeProfilerAction, edge_annotate, "Perform edge annotation pass")

void EdgeProfilerAnnotationPass::_run(IRManager& irm) {
    ControlFlowGraph& flowGraph = irm.getFlowGraph();
    MethodDesc& md = irm.getMethodDesc();
    MemoryManager mm("Edge AnnotationPass");
    bool debug = Log::isEnabled();
    EdgeProfilerAction* action = (EdgeProfilerAction*)getAction();
    const EdgeProfileFlags& flags = action->getFlags();

    if (debug) {
        Log::out()<<"EdgeProfilerAnnotationPass. BcLevel="<<flags.bcLevelProfiling<<std::endl;
    }


    // Create the edge profile structure for the compiled method in 'irm'.
    ProfilingInterface* pi = irm.getProfilingInterface();
    bool edgeProfilerMode = pi->isProfilingEnabled(ProfileType_Edge, JITProfilingRole_USE);
    bool entryBackedgeProfilerMode = !edgeProfilerMode && pi->isProfilingEnabled(ProfileType_EntryBackedge, JITProfilingRole_USE);
    U_32 entryCount = (edgeProfilerMode || entryBackedgeProfilerMode) ? pi->getProfileMethodCount(md) : 0;
    if (isMethodTrivial(flowGraph) || !edgeProfilerMode || entryCount == 0) { 
        // Annotate the CFG using static profiler heuristics.
        if (debug) {
            Log::out()<<"Using static profiler to estimate trivial graph"<<std::endl;
        }
        StaticProfiler::estimateGraph(irm, entryCount);
        return;
    }
        
    OptPass::computeDominatorsAndLoops(irm);
    DominatorTree* dt = irm.getDominatorTree();

    LoopTree* lt = irm.getLoopTree();

    LogStream& irdump = log(LogStream::IRDUMP);
    if (irdump.isEnabled()) {
        printHIR(irm, "IR before instrumentation");
    }

    // sync checksum
    StlSet<Node*> nodesToIgnore(mm); //see instrumentation pass for comments
    selectNodesToIgnore(irm, lt, nodesToIgnore, flags.bcLevelProfiling);

    U_32 cfgCheckSum = computeCheckSum(mm, irm, nodesToIgnore, flags.bcLevelProfiling);

    EdgeMethodProfile* edgeProfile = pi->getEdgeMethodProfile(mm, md);
    U_32 profileCheckSum = edgeProfile->getCheckSum();
    //assert(profileCheckSum == cfgCheckSum);
    if (cfgCheckSum == profileCheckSum) {
        // Start propagating the CFG from instrumented edges.
        Edges edges(mm);
        selectEdgesToInstrument(mm, irm, edges, nodesToIgnore, flags.bcLevelProfiling);
        //assert if num counters is not equal -> must be guaranteed after checksum check
        //for BC-level profiling checksum calculation is simplified -> no assertion
        assert(edges.size() == edgeProfile->getNumCounters() || flags.bcLevelProfiling);
        bool res = calculateProbsFromProfile(mm, flowGraph, edges, dt, lt, edgeProfile, flags.bcLevelProfiling, nodesToIgnore);
        if (res) {
            flowGraph.setEdgeProfile(true);
        }
    }
    if (!flowGraph.hasEdgeProfile()) {
        if (debug) {
            Log::out()<<"DynProf failed: using static profiler to estimate graph!"<<std::endl;
        }
        StaticProfiler::estimateGraph(irm, 10000, true);
    }
    if (irm.getParent() == NULL) {
        // fix profile: estimate cold paths that was never executed and recalculate frequencies
        StaticProfiler::fixEdgeProbs(irm); 
        flowGraph.smoothEdgeProfile();
    }
}

static inline void setEdgeFreq(StlVector<double>& edgeFreqs, Edge* edge, double freq, bool debug) {
    if (debug) {
        Log::out()<<"\t settings edge(id="<<edge->getId()<<") freq ("; FlowGraph::printLabel(Log::out(), edge->getSourceNode());
        Log::out() << "->"; FlowGraph::printLabel(Log::out(), edge->getTargetNode()); Log::out()<<") to "<<freq << std::endl;
    }
    assert(freq>=0);
    edgeFreqs[edge->getId()] = freq;
}

static void updateDispatchPathsToCatch(Node* node, StlVector<double>& edgeFreqs, bool debug) {
    double freq =  node->getExecCount();
    const Edges& inEdges = node->getInEdges();
    for (Edges::const_iterator it = inEdges.begin(), end = inEdges.end(); it!=end; ++it) {
        Edge* edge = *it;
        Node* srcNode = edge->getSourceNode();
        if (srcNode->isDispatchNode() && freq > edgeFreqs[edge->getId()]) {
            setEdgeFreq(edgeFreqs, edge, freq, debug);
            srcNode->setExecCount(std::max(0.0, srcNode->getExecCount()) + freq);
            updateDispatchPathsToCatch(srcNode, edgeFreqs, debug);
        }
    }
}

static bool calculateProbsFromProfile(MemoryManager& mm, ControlFlowGraph& fg, const Edges& pEdges, 
                                      DominatorTree* dt, LoopTree* lt, EdgeMethodProfile* profile, 
                                      bool bcLevelProfiling, const StlSet<Node*>& nodesToIgnore) 
{
    //calculate edge freqs and use them to calculate edge probs.

    bool debug = Log::isEnabled();
    if (debug) {
        Log::out()<<"Starting probs calculation" <<std::endl;
    }
    U_32 entryCount = *profile->getEntryCounter();
 
    //1. assign default value to nodes and edges, this value is used for consistency checks latter
    StlVector<Node*> nodes(mm);
    fg.getNodesPostOrder(nodes); 
    for (StlVector<Node*>::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) {
        Node* node = *it;
        node->setExecCount(-1);
        const Edges& edges = node->getOutEdges();
        for (Edges::const_iterator it2 = edges.begin(), end2 = edges.end(); it2!=end2; ++it2) {
            Edge* edge = *it2;
            edge->setEdgeProb(-1);
        }
    }
    
    //2. calculate edge-freq for every edge.
    
    //2.1 get freqs from profile
    StlVector<double> edgeFreqs(mm, fg.getMaxEdgeId(), -1);
    U_32 n = 1;
    for (Edges::const_iterator it = pEdges.begin(), end = pEdges.end(); it!=end; ++it, ++n) {
        Edge* edge = *it;
        U_32 key = genKey(n, edge, bcLevelProfiling, debug);
        U_32* counterAddr = profile->getCounter(key);
        //assert(bcLevelProfiling || counterAddr!=NULL); -> TODO: hits in lazy resolution mode
        U_32 freq = 0;
        if (counterAddr == NULL) {
            if (!bcLevelProfiling) { //avoid crash, use static profiler for a method
                return false;
            }
        }  else {
            freq = *counterAddr;
        }

        setEdgeFreq(edgeFreqs, edge, freq, debug);
    }

    //2.2 propagate edge frequencies on linear paths
    // this operation is needed because we do not instrument artificial edges (edges that connect nodes with the same bc-mapping)
    if (bcLevelProfiling) {
        for (StlVector<Node*>::reverse_iterator it = nodes.rbegin(), end = nodes.rend(); it!=end; ++it) {
            Node* node = *it;
            const Edges& outEdges = node->getOutEdges();
            for (Edges::const_iterator it2 = outEdges.begin(), end2 = outEdges.end(); it2!=end2; ++it2) {                    
                Edge* edge = *it2;
                double freq = edgeFreqs[edge->getId()];
                if (freq==-1) { //this edge has no profile -> can't use it for propagation
                    continue;
                }
                Node* targetNode = edge->getTargetNode();
                //check pattern for artificial nodes: 1 unconditional + no changes in bcmapping
                if (targetNode->isBlockNode() && targetNode->getOutDegree() <= 2 && targetNode->getUnconditionalEdge()!=NULL) { 
                    Edge* unconditionalEdge = targetNode->getUnconditionalEdge();
                    if (targetNode->getFirstInst()->getBCOffset() == unconditionalEdge->getTargetNode()->getFirstInst()->getBCOffset()) {
                        double ufreq = edgeFreqs[unconditionalEdge->getId()];
                        double newUFreq= freq + MAX(ufreq, 0);
                        if (debug) {
                            Log::out()<<"Restoring profile for artificial edge : edge-id="<<unconditionalEdge->getId()<<std::endl;
                        }
                        setEdgeFreq(edgeFreqs, unconditionalEdge, newUFreq, debug);

                    }
                }
            }
        }
    }
    
    
    //2.3 fix catch freqs, so we will have estimated D->C edges
    if (debug) {
        Log::out()<<"\tFixing catch freqs"<<std::endl;
    }
    for (StlVector<Node*>::reverse_iterator it = nodes.rbegin(), end = nodes.rend(); it!=end; ++it) {
        Node* node = *it;
        bool ignored = nodesToIgnore.find(node)!=nodesToIgnore.end();
        if (!node->isCatchBlock() || ignored) { 
            continue;
        }
        //set up catch block prob -> will be used for dispatch nodes.
        double nodeFreq = 0;
        const Edges& outEdges = node->getOutEdges();
        for (Edges::const_iterator it2 = outEdges.begin(), end2 = outEdges.end(); it2!=end2; ++it2) {                    
            Edge* edge = *it2;
            double edgeFreq = edgeFreqs[edge->getId()];
            edgeFreq = MAX(0, edgeFreq); //if Cn->Ln edge is marked as artificial it's not instrumented
            nodeFreq+=edgeFreq;
        }
        node->setExecCount(nodeFreq);
        if (debug) {
            Log::out()<<"\t\t fixing catch node ";FlowGraph::printLabel(Log::out(), node);Log::out()<<" freq="<<nodeFreq<<std::endl;
        }
        updateDispatchPathsToCatch(node, edgeFreqs, debug);
    }

    //2.4 calculate freqs for every edge in topological order
    // set up nodes exec count for every node.
    if (debug) {
        Log::out()<<"\tPropagating edge freqs"<<std::endl;
    }
    for (StlVector<Node*>::reverse_iterator it = nodes.rbegin(), end = nodes.rend(); it!=end; ++it) {
        Node* node = *it;
        bool ignored = nodesToIgnore.find(node)!=nodesToIgnore.end();
        double nodeFreq = 0;
        const Edges& outEdges = node->getOutEdges();
        const Edges& inEdges = node->getInEdges();
        if (debug) {
            Log::out()<<"\t\tNode="; FlowGraph::printLabel(Log::out(), node);Log::out()<<" in-edges="<<inEdges.size() << " was ignored="<<ignored<<std::endl;
        }
        if (node->getInDegree() == 0) {
            assert(node == fg.getEntryNode());
            nodeFreq = entryCount;
        } else if (node->isCatchBlock()) { //set up catch block prob -> will be used for dispatch nodes.
            if (ignored) { 
                // ignored catch edge (successor of ignored node or catch-loop)
                // max we can do here is to try to get catch freq from in-edge
                double _freq = 0;
                Edge* inEdge  = *node->getInEdges().begin();
                if (node->getInDegree() == 1 && edgeFreqs[inEdge->getId()]>=0) {
                    _freq = edgeFreqs[inEdge->getId()];
                } 
                Edge* outEdge = *node->getOutEdges().begin();
                nodeFreq = edgeFreqs[outEdge->getId()] = _freq;
            } else {//all out-edges were instrumented -> easy to calculate freq
                nodeFreq = node->getExecCount(); //already assigned
                assert(nodeFreq>=0);
            } 
        } else {
            for (Edges::const_iterator it2 = inEdges.begin(), end2 = inEdges.end(); it2!=end2; ++it2) {
                Edge* edge = *it2;
                Node* srcNode = edge->getSourceNode();
                //assign edge-freq when available 
                //or 0-freq when source is dispatch (catches handled separately)
                //or freq of src node when src node was removed from instrumentation(equal freq for all out-edges)
                double edgeFreq = 0;
                if (nodesToIgnore.find(srcNode)!=nodesToIgnore.end()) {
                    assert(srcNode->getExecCount()!= -1 || (srcNode->isCatchBlock() && dt->dominates(node, srcNode)) || (hasCatch(node) && srcNode->isEmpty()));
                    edgeFreq = srcNode->getExecCount();
                } else if (srcNode->isBlockNode()) {
                    edgeFreq = edgeFreqs[edge->getId()];
                }
                if (debug) {
                    Log::out()<<"\t\t\tedge id="<<edge->getId()<<" from="; FlowGraph::printLabel(Log::out(), srcNode);
                    Log::out()<<" freq="<<edgeFreq<<std::endl;
                }
                if (edgeFreq == -1) {
                    //the only way to get not estimated edge here is to have catch  loops (monexit pattern)
#ifdef _DEBUG
                    Node* head = lt->getLoopHeader(node, false); //catch loops are not instrumented
                    assert(head != NULL && (head->isCatchBlock() || head->isDispatchNode() || hasCatch(head)));
#endif
                    edgeFreq = 0;
                    setEdgeFreq(edgeFreqs, edge, edgeFreq, debug);
                }
                nodeFreq +=edgeFreq;
            }
        }
        if (debug) {
            Log::out()<<"\t\t\tnode freq="<<nodeFreq<<std::endl;
        }
        assert(nodeFreq!=-1);
        node->setExecCount(nodeFreq);
        if (node->isExitNode()) {
            continue;
        }
        //now we able to calculate all outgoing edge freqs for current node
        //if node is bb -> only 1 edge is allowed to be without freq here and we will fix it
        //if node is dispatch -> use catch node freqs
        //if node was ignored -> equal freq for every bb edge, 0 to dispatch edge
        double freqLeft = nodeFreq;
        if (ignored) {
            if ( outEdges.size()==1 ) {
                Edge* edge = *outEdges.begin();
                setEdgeFreq(edgeFreqs, edge, nodeFreq, debug);
            } else {
                double freqPerBB = nodeFreq / (outEdges.size() - (node->getExceptionEdge() == NULL ? 0 : 1));
                for (Edges::const_iterator it = outEdges.begin(), end = outEdges.end(); it!=end; ++it) {
                    Edge* edge = *it;
                    setEdgeFreq(edgeFreqs, edge, edge->getTargetNode()->isBlockNode() ? freqPerBB : 0, debug);
                }
            }
        } else if (node->isBlockNode()) {
            Edge* notEstimatedEdge = NULL;
            for (Edges::const_iterator it2 = outEdges.begin(), end2 = outEdges.end(); it2!=end2; ++it2) {
                Edge* edge = *it2;
                double edgeFreq = edgeFreqs[edge->getId()];
                if (edgeFreq != -1) {
                    freqLeft-=edgeFreq;
                } else {
                    // here we can have 2 not-estimated edges only of this block was connected to 'ignored' node during annotation.
                    if (notEstimatedEdge == NULL) {
                        notEstimatedEdge = edge;   
                    } else if (notEstimatedEdge->getTargetNode()->isDispatchNode()) {
                        setEdgeFreq(edgeFreqs, notEstimatedEdge, 0, debug);
                        notEstimatedEdge = edge;
                    } else {
                        setEdgeFreq(edgeFreqs, edge, 0, debug);
                    }
                }
            }
            if (notEstimatedEdge!=NULL) {
                freqLeft = freqLeft < 0 ? 0 : freqLeft;
                setEdgeFreq(edgeFreqs, notEstimatedEdge, freqLeft, debug);
            } 
        } else if (node->isDispatchNode()) {
            //for all not estimated on step 2.2 D->X edges set edge prob to min (0). 
            for (Edges::const_iterator it = outEdges.begin(), end = outEdges.end(); it!=end; ++it) {
                Edge* edge = *it;
                double _freq = edgeFreqs[edge->getId()];
                if (_freq==-1) {
                    setEdgeFreq(edgeFreqs, edge, 0, false);
                }     
            }
        } 
    }
    
   
    //3. calculate edge probs using edge freqs. 
    if (debug) {
        Log::out()<<"Calculating edge probs using freqs.."<<std::endl;
    }
    for (StlVector<Node*>::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it, n++) {
        Node* node = *it;
        double nodeFreq = node->getExecCount();
        assert(nodeFreq!=-1);
        const Edges& edges = node->getOutEdges();
        for (Edges::const_iterator it2 = edges.begin(), end2 = edges.end(); it2!=end2; ++it2) {
            Edge* edge = *it2;
            double edgeFreq =edgeFreqs[edge->getId()];
            assert(edgeFreq!=-1);
            double edgeProb = nodeFreq == 0 ? 0 : edgeFreq / nodeFreq ;
//            assert(edgeProb >= 0 && edgeProb <= 1);
            edge->setEdgeProb(edgeProb);
        }
    }
    if (debug) {
        Log::out()<<"Finished probs calculation";
    }
    return true;
}

//
// Compute the checksum contribution of the given Edge
//
static U_32 _computeCheckSum(Node* node, const StlSet<Node*>& nodesToIgnore, StlVector<bool>& flags, U_32 depth, bool debug) {
    assert(flags[node->getId()] == false);
    flags[node->getId()] = true;
    //node is removed from checksum calculation if 
    // 1) it's in ignore list
    // 2) it's dispatch or catch -> due to the fact that ignore-list nodes can add more dispatches & catches(finally-blocks)
    bool ignored = nodesToIgnore.find(node)!=nodesToIgnore.end();
    bool skipped = ignored || node->getOutDegree()==1
        || (node->isCatchBlock() && node->isEmpty()) || node->isDispatchNode() || node->isExitNode(); 
    U_32 dSum = skipped ? 0 : depth;
    U_32 childDepth = skipped ? depth : depth + 1;
    const Edges& outEdges = node->getOutEdges();
    U_32 childsSum = 0;
    for (Edges::const_iterator it = outEdges.begin(), end = outEdges.end(); it!=end; ++it) {
        Edge* edge = *it;
        Node* childNode = edge->getTargetNode();
        //visit only those not visited child nodes that are not dispatch edges of ignored nodes
        if (flags[childNode->getId()] == false && !(ignored && childNode->isDispatchNode())) { 
            childsSum+=_computeCheckSum(childNode, nodesToIgnore, flags, childDepth, debug);
        } 
    }
    if (debug){
        Log::out()<< "\t<checksum calculation: node:"; FlowGraph::printLabel(Log::out(), node); 
        Log::out() << "=+"<<dSum<<"  depth="<<depth<< " child sum="<<childsSum<<std::endl;
    }
    return dSum+childsSum;
}

static U_32 computeCheckSum( MemoryManager& mm, IRManager& irm,  const StlSet<Node*>& nodesToIgnore, bool bcLevel) {
    bool debug = Log::isEnabled();
    if (debug) {
        Log::out()<< "calculating checksum.." << std::endl;
    }
    U_32 checkSum = 0;
    if (!bcLevel) {
        ControlFlowGraph& cfg = irm.getFlowGraph();
        StlVector<bool> flags(mm, cfg.getMaxNodeId(), false);
        checkSum = _computeCheckSum(cfg.getEntryNode(), nodesToIgnore, flags, 1, debug);
    } else {
        checkSum = irm.getMethodDesc().getByteCodeSize();
    }
    if( debug){
        Log::out()<< "checkSum= "<<checkSum<<std::endl;
    }
    return checkSum;
}


static Node* selectNodeToInstrument(IRManager& irm, Edge* edge) {
    ControlFlowGraph& fg = irm.getFlowGraph();
    Node* srcNode = edge->getSourceNode();
    Node* dstNode = edge->getTargetNode();
    Node* result = NULL;
    assert(srcNode->isBlockNode() && dstNode->isBlockNode());
    if (srcNode->isCatchBlock()) { 
        // catch blocks handled separately. We must add counter only after catch inst
        assert(srcNode->hasOnlyOneSuccEdge() || hasCatch(srcNode));
        if (srcNode->hasOnlyOneSuccEdge() && hasCatch(srcNode)) { //filter-out catches with ret -> instrument srcNode 
            result = srcNode;
        } else {
            result = dstNode;
        }
    } else { 
        result = srcNode->hasOnlyOneSuccEdge() ? srcNode : dstNode;
    } 
    if( result->hasTwoOrMorePredEdges() ){
        // Splice a new block on edge from srcNode to dstNode and put 
        // instrumentation code there.
        result = fg.spliceBlockOnEdge(edge, irm.getInstFactory().makeLabel());
    } 
    return result;
}

static bool hasCatch( Node* node ) {
    Inst* inst = (Inst*)node->getFirstInst();
    assert(inst->isLabel());
    // Op_Catch is allowed to be not in the second position only (after label inst) 
    // but in arbitrary position if Op_Phi insts present.
    do {
        inst = inst->getNextInst();
    } while (inst!=NULL && inst->getOpcode() == Op_Phi);
    return inst != NULL && inst->getOpcode() == Op_Catch;
}

/*static bool hasCounter( Node* node ) {
    for (Inst* inst =  node->getFirstInst()->next(); inst!=node->getFirstInst(); inst = inst->next()) {
        if (inst->getOpcode() == Op_IncCounter) {
            return true;
        }
    }
    return false;
    
}*/

static void selectNodesToIgnore(IRManager& irm, LoopTree* lt, StlSet<Node*>& result, bool bcLevel) {
    ControlFlowGraph& fg = irm.getFlowGraph();
    bool debug = Log::isEnabled();
    if (debug) {
        Log::out() << "Selecting nodes to ignore:"<<std::endl;
    }

    const Nodes& nodes = fg.getNodes();
    for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) {
        Node* node = *it;
        //first pattern to ignore: class initializers in non-bc-level mode
        Node* loopHead = lt->getLoopHeader(node, false);
        bool inCatchLoop = loopHead!=NULL && (loopHead->isCatchBlock() || loopHead->isDispatchNode() || hasCatch(loopHead));
        if (!bcLevel && node->isBlockNode()  
            && node->getOutDegree() == 2  && node->getExceptionEdge()!=NULL 
            && ((Inst*)node->getLastInst())->getOpcode() == Op_InitType) 
        {
            result.insert(node);
            if (debug) {
                Log::out() << "\tIgnoring Op_InitType node:";FlowGraph::printLabel(Log::out(), node);Log::out() << std::endl;
            }
        } else if (inCatchLoop && node->isEmpty()) {
            //common block for multiple catches in catch loop -> add to ignore
            result.insert(node);
            if (debug) {
                Log::out() << "\tIgnoring catch-loop preheader node:";FlowGraph::printLabel(Log::out(), node);Log::out() << std::endl;
            }
        } else if (node->isCatchBlock()) {  
            Node* blockWithCatchInst = NULL;
            if (hasCatch(node)) {
            //    blockWithCatchInst = node; //TODO: recheck
            } else {
                assert(node->hasOnlyOneSuccEdge());
                Edge* e =  *node->getOutEdges().begin();
                blockWithCatchInst = e->getTargetNode();
            }
            if (blockWithCatchInst!=NULL && blockWithCatchInst->hasTwoOrMorePredEdges()) { //avoid mon-exit loops (catch loops) instrumentation
                result.insert(node);
                if (debug) {
                    Log::out() << "\tIgnoring '1-catch-inst*N-catches' node:";FlowGraph::printLabel(Log::out(), node);Log::out() << std::endl;
                }
            }
        }
    }
    if (debug) {
        Log::out() << "DONE. ignored nodes: " << result.size() << std::endl;
    }
}

static void _selectEdgesToInstrument(Node* srcNode, IRManager& irm, Edges& result,
                                     const StlSet<Node*>& nodesToIgnore,  StlVector<bool>& flags, bool bcLevel) 
{
    bool profileDispatchEdges = true; //TODO: cmd-line param

    assert(flags[srcNode->getId()] == false);
    flags[srcNode->getId()] = true;
    Node* returnNode = irm.getFlowGraph().getReturnNode();
    LoopTree* loopTree = irm.getLoopTree();
    const Edges& oEdges = srcNode->getOutEdges();
    bool ignored = nodesToIgnore.find(srcNode)!=nodesToIgnore.end();
    if (!ignored && srcNode->isBlockNode()) {
        Edge* skipEdge = NULL; //instrument all edges except one
        if (srcNode->isCatchBlock()) {
            // for a catch block we can have only 1 successor edge if catch inst is in next block
            // if catch inst is in catch block -> instrument every outgoing edge to be able to restore catch
            // node frequency.
            assert(hasCatch(srcNode) || srcNode->hasOnlyOneSuccEdge());
        } else if (!bcLevel) { //instrument all edges if bcLevel profiling. Artificial edges will be filtered later
            for(Edges::const_iterator it = oEdges.begin(); it!= oEdges.end(); ++it ){
                Edge* edge = *it;
                Node* targetNode = edge->getTargetNode();
                bool isBackEdge = loopTree->isBackEdge(edge);
                //we must instrument backedges to be able to restore loop iteration count
                if( isBackEdge || (!targetNode->isBlockNode() && profileDispatchEdges) ){
                    // We run into a dispatch node, so we have to instrument all the other edges.
                    skipEdge = NULL;
                    break;
                }
                // It is profitable to instrument along the loop exit edge.
                if (skipEdge == NULL || loopTree->isLoopExit(skipEdge)) {
                    skipEdge = edge; 
                }  
            }
        }
        bool debug = Log::isEnabled();
        for(Edges::const_iterator it = oEdges.begin(); it!= oEdges.end(); ++it ){
            Edge* edge = *it;
            Node* targetNode = edge->getTargetNode();
            if( targetNode->isBlockNode() && edge!=skipEdge){
                bool skip = false;
                if (bcLevel && targetNode->getNodeStartBCOffset() == edge->getSourceNode()->getNodeEndBCOffset()) {
                    skip = true;//skip this edge, it's artificial code
                }
                if (bcLevel && targetNode == returnNode) {
                    skip = true;
                }
                if (!skip) {
                    result.push_back(edge);
                } 
                if (debug) {
                    Log::out()<<"\tedge id="<<edge->getId()<<" ("; FlowGraph::printLabel(Log::out(), edge->getSourceNode());
                    Log::out()<<"->"; FlowGraph::printLabel(Log::out(), edge->getTargetNode());Log::out()<<")";
                    if (skip) Log::out()<<" SKIPPED as artificial ";
                    Log::out()<<std::endl;
                }
            }
        }
    }
    // process all child nodes. for ignored nodes we do not process dispatches 
    // because new catch block can be created that must also be ignored
    for(Edges::const_iterator it = oEdges.begin(); it!= oEdges.end(); ++it ){
        Edge* edge = *it;
        Node* targetNode = edge->getTargetNode();
        if (flags[targetNode->getId()] == false && !(ignored && targetNode->isDispatchNode())) {
            _selectEdgesToInstrument(targetNode, irm, result, nodesToIgnore, flags, bcLevel);
        }
    }
}

static void selectEdgesToInstrument(MemoryManager& mm, IRManager& irm, Edges& result,  
                                    const StlSet<Node*>& nodesToIgnore, bool bcLevel) 
{
    ControlFlowGraph& fg = irm.getFlowGraph();
    StlVector<bool> flags(mm, fg.getMaxNodeId(), false);

    bool debug = Log::isEnabled();
    if (debug) {
        Log::out() << "List of edges to instrument: "<<std::endl;
    }
    _selectEdgesToInstrument(fg.getEntryNode(), irm, result, nodesToIgnore, flags, bcLevel);
    if (debug) {
        Log::out() << "End of list.."<<std::endl;
    }
}

//
// Return true if the method represented by <cfg> is trivial.
// A method is trivial if it is a leaf method, and it has no if-then-else
// statement.
//
static bool isMethodTrivial( ControlFlowGraph& cfg ) {
    const Nodes& nodes = cfg.getNodes();
    Nodes::const_iterator niter;

    for( niter = nodes.begin(); niter != nodes.end(); niter++ ){
        Node* node = *niter;
        if( !node->isBlockNode() || node->isEmpty() ){
            continue;
        }
        Inst* last = (Inst*)node->getLastInst();
        // This method is not a leaf method.
        if( last->getOpcode() >= Op_DirectCall && last->getOpcode() <= Op_VMHelperCall ){
            return false;
        }
        Edges::const_iterator eiter;
        const Edges& oEdges = node->getOutEdges();
        int succ = 0;

        for(eiter = oEdges.begin(); eiter != oEdges.end(); ++eiter) {
            Edge* edge = *eiter;
            if( edge->getTargetNode()->isBlockNode() ){
                succ++;
            }
        }
        // This method has if-then-else statement(s).
        if( succ > 1 ){
            return false;
        }
    }
    return true;
}

static U_32 genKey( U_32 pos, Edge* edge, bool bcLevel, bool debug)  {
    U_32 key = 0;
    if (debug) {
        Log::out()<<"\t\t key for edge with id="<<edge->getId()<<" ("; FlowGraph::printLabel(Log::out(), edge->getSourceNode());
        Log::out() << "->"; FlowGraph::printLabel(Log::out(), edge->getTargetNode()); Log::out()<<") is ";Log::out().flush();
    }
    if (bcLevel) {
        uint16 bcBefore = edge->getSourceNode()->getNodeEndBCOffset();
        uint16 bcAfter  = edge->getTargetNode()->getNodeStartBCOffset();
        assert(bcBefore!=ILLEGAL_BC_MAPPING_VALUE && bcAfter!=ILLEGAL_BC_MAPPING_VALUE);
        key = (((U_32)bcBefore)<<16) + bcAfter;
    } else {
        //TODO: this algorithm is not 100% effective: we can't rely on edges order in CFG
        U_32 edgePos = 0;
        const Edges& edges = edge->getSourceNode()->getOutEdges();
        for (Edges::const_iterator it = edges.begin(), end = edges.end(); it!=end; ++it) {
            Edge* outEdge = *it;
            if (outEdge == edge) {
                break;
            }
            if (outEdge->isDispatchEdge()) { //dispatch edge order is the reason of the most of the edge ordering errors 
                continue;
            }
            edgePos++;
        }

        key = pos + (edgePos << 16);
    }
    if (debug) {
        Log::out() << key << std::endl;
    }
    return key;
}

static void checkBCMapping( ControlFlowGraph& cfg ) {
#ifdef _DEBUG
    const Nodes& nodes = cfg.getNodes();
    for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) {
       Node* node = *it;
        if (node->isBlockNode() && node!=cfg.getReturnNode()) {
            CFGInst* inst = node->getFirstInst();
            assert(inst!=NULL && inst->isLabel());
            if (inst->getBCOffset()==ILLEGAL_BC_MAPPING_VALUE) {
                if (Log::isEnabled()) {
                    Log::out()<<"Illegal BC-Map for node:";FlowGraph::printLabel(Log::out(), node);
                }
                assert(inst->getBCOffset()!=ILLEGAL_BC_MAPPING_VALUE);
            }
        }
    }
#endif
}
} //namespace