/*
 *  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 "ControlFlowGraph.h"
#include "LoopTree.h" //required for edge profile smoothing
#include <algorithm>

namespace Jitrino {

//////////////////////////////////////////////////////////////////////////
// ControlFlowGraphFactory methods
Node* ControlFlowGraphFactory::createNode(MemoryManager& mm, Node::Kind kind) {
    return new (mm) Node(mm, kind);
}    

Edge* ControlFlowGraphFactory::createEdge(MemoryManager& mm, Node::Kind srcKind, Node::Kind dstKind) {
    return new (mm) Edge();
}


//////////////////////////////////////////////////////////////////////////
// Edge methods

Edge::Kind Edge::getKind() const {
    Edge::Kind kind = Edge::Kind_Unconditional;
    if (source->isBlockNode()) {
        if (target->isBlockNode()) {
            if (source->getOutDegree() > 1) {
                CFGInst* inst = source->getLastInst();
                if (inst!=NULL) {
                    kind = inst->getEdgeKind(this);
                } else { //empty node with dispatch and unconditional edges. B->B edge is unconditional
#ifdef _DEBUG       //do some checks
                    assert(source->getOutDegree() == 2);
                    const Edges& outEdges = source->getOutEdges();
                    Edge* secondEdge  = outEdges.front() == this ? outEdges.back() : outEdges.front();
                    assert(secondEdge->getTargetNode()->isDispatchNode());
#endif
                    //edge kind stays unconditional
                }
            }
        } else if (target->isDispatchNode()) {
            kind = Edge::Kind_Dispatch;
        } else {
            assert(target->isExitNode());//kind is unconditional
        }
    } else {
        assert(source->isDispatchNode());
        if (target->isDispatchNode() || target->isExitNode()) {
            kind = Edge::Kind_Dispatch;
        } else {
            assert(target->isBlockNode());
            kind = Edge::Kind_Catch;
        }
    }
    return kind;
}

//////////////////////////////////////////////////////////////////////////
// Node methods

class HeadInst : public CFGInst {
public:
    HeadInst(Node* _node) {node = _node;}
    // must never be called on head inst
    virtual Edge::Kind getEdgeKind(const Edge* edge) const {assert(false); return Edge::Kind_Unconditional;}
};

Node::Node(MemoryManager& mm, Kind _kind)
: id(MAX_UINT32), dfNumber(0), preNumber(0), postNumber(0), traversalNumber(0), 
kind(_kind), inEdges(mm), outEdges(mm), instsHead(NULL), execCount(0)
{
    instsHead = new (mm) HeadInst(this);
}

Edge* Node::getOutEdge(Edge::Kind edgeKind) const {
    for (Edges::const_iterator ite = outEdges.begin(), ende = outEdges.end(); ite!=ende; ++ite) {
        Edge* edge = *ite;
        if (edge->getKind() == edgeKind) {
            return edge;
        }
    }
    return NULL;
}


Edge* Node::findEdge(bool isForward, const Node* node) const {
    const Edges& edges = getEdges(isForward);
    for (Edges::const_iterator ite = edges.begin(), ende = edges.end(); ite!=ende; ++ite) {
        Edge* edge = *ite;
        if (edge->getNode(isForward) == node) {
            return edge;
        }
    }
    return NULL;
}


// appends inst to the end of node list.
void Node::appendInst(CFGInst* newInst, CFGInst* instAfter) {
    if (instAfter==NULL) {
        newInst->insertBefore(instsHead);
    } else {
        assert(instAfter->getNode() == this);
        newInst->insertAfter(instAfter);
    }
    
}

// appends inst to the beginning of node list. Checks "block header critical inst" property
void Node::prependInst(CFGInst* newInst, CFGInst* instBefore) {
    if (instBefore==NULL) {
        instBefore = instsHead;
        for (CFGInst* inst = getFirstInst(); inst!=NULL; inst = inst->next()) {
            if (inst->isLabel()) {
                continue;
            }
            if (newInst->isHeaderCriticalInst() || !inst->isHeaderCriticalInst()) {
                instBefore = inst;
                break;
            }
        }
    }
    assert(instBefore->getNode() == this);
    newInst->insertBefore(instBefore);
}

void Node::insertInst(CFGInst* prev, CFGInst* newInst) {
#ifdef _DEBUG
    assert(newInst->getNode() == NULL);
    if (newInst->isHeaderCriticalInst()) { //check prev inst is also critical
        if (prev != instsHead) { //check only if newInst will not be the first
            CFGInst* prevInst = (CFGInst*)prev;
            assert(prevInst->isHeaderCriticalInst());
            assert(!newInst->isLabel()); //label must be the first
        } 
    } else { //check next inst is not critical
        Dlink* nextLink = prev->getNext();
        if (nextLink!=instsHead) {//check only if newInst will not be the last
            CFGInst* nextInst = (CFGInst*)nextLink;
            assert(!nextInst->isHeaderCriticalInst());
        }
    }
#endif
    ((Dlink*)newInst)->insertAfter(prev);
    newInst->node = this;
}


U_32 Node::getInstCount(bool ignoreLabels) const  {
    U_32 count = 0;
    CFGInst* first = getFirstInst();
    while (ignoreLabels && first!=NULL && first->isLabel()) {
        first = first->next();
    }
    for (CFGInst* inst = first; inst!=NULL; inst = inst->next()) {
        count++;
    }
    return count;
}

Edge* Node::findEdgeTo(bool isForward, Node* node) const {
    const Edges& edges = getEdges(isForward);
    for (Edges::const_iterator ite = edges.begin(), ende = edges.end(); ite!=ende; ++ite) {
        Edge* edge = *ite;
        if (edge->getNode(isForward) == node) {
            return edge;
        }
    }
    return NULL;

}

uint16 Node::getNodeStartBCOffset() const {
    if (!isBlockNode()) {
        return ILLEGAL_BC_MAPPING_VALUE;
    }
    CFGInst* inst = getFirstInst();
    while (inst!=NULL && inst->getBCOffset()==ILLEGAL_BC_MAPPING_VALUE) {
        inst = inst->next();
    }
    return inst==NULL ? ILLEGAL_BC_MAPPING_VALUE : inst->getBCOffset();
}

uint16 Node::getNodeEndBCOffset() const {
    if (!isBlockNode()) {
        return ILLEGAL_BC_MAPPING_VALUE;
    }
    CFGInst* inst = getLastInst();
    while (inst!=NULL && inst->getBCOffset()==ILLEGAL_BC_MAPPING_VALUE) {
        inst = inst->prev();
    }
    return inst==NULL ? ILLEGAL_BC_MAPPING_VALUE : inst->getBCOffset();
}


//////////////////////////////////////////////////////////////////////////
// CFG methods

ControlFlowGraph::ControlFlowGraph(MemoryManager& _mm, ControlFlowGraphFactory* _factory) 
: mm (_mm), factory(_factory), entryNode (NULL), returnNode(NULL), exitNode(NULL), unwindNode(NULL),
nodes(_mm), postOrderCache(_mm), nodeIDGenerator(0), edgeIDGenerator(0), nodeCount(0), 
traversalNumber(0), lastModifiedTraversalNumber(0), lastOrderingTraversalNumber(0),
lastEdgeRemovalTraversalNumber(0), lastProfileUpdateTraversalNumber(0), currentPreNumber(0), currentPostNumber(0),
annotatedWithEdgeProfile(false), domTree(NULL), postDomTree(NULL), loopTree(NULL)
{
    if (factory == NULL) { //use default factory
        factory = new (mm) ControlFlowGraphFactory();
    }
}

Node* ControlFlowGraph::createNode(Node::Kind kind, CFGInst* inst) {
    Node* node = factory->createNode(mm, kind);
    addNode(node);
    if (inst!=NULL) {
        node->appendInst(inst); 
    }
    return node;
}


void ControlFlowGraph::removeNode(Node* node) {
    removeNode(std::find(nodes.begin(), nodes.end(), node), true);
}

void ControlFlowGraph::removeNode(Nodes::iterator pos, bool erase) {
    Node* node = *pos;
    
	if (node == entryNode) {
		entryNode=NULL;
	}
    if (node == returnNode) {
        returnNode = NULL;
    } else if(node == unwindNode) {
        unwindNode = NULL;
    } else  if (node == exitNode) {
        exitNode = NULL;
    }
    
    // Remove incident edges
    while (!node->inEdges.empty()) {
        Edge* edge = node->inEdges.front();
        assert(edge->getTargetNode() == node);
        removeEdge(edge);
    }
    
    while (!node->outEdges.empty()) {
        Edge* edge = node->outEdges.front();
        assert(edge->getSourceNode() == node);
        removeEdge(edge);
    }

    // Erase the node itself
    if (erase) {
        *pos = *nodes.rbegin();
        nodes.pop_back();
    } else {
        *pos = NULL;
    }

    // Mark the graph modified.
    lastModifiedTraversalNumber = traversalNumber;
}

Edge* ControlFlowGraph::addEdge(Node* source, Node* target, double edgeProb) {
    assert(target!=entryNode);
    assert(source!=exitNode);
    assert (source->findTargetEdge(target) == NULL);
    Edge* edge = factory->createEdge(mm, source->getKind(), target->getKind());
    addEdge(source, target, edge, edgeProb);
    return edge;
}

void ControlFlowGraph::addEdge(Node* source, Node* target, Edge* edge, double edgeProb) {
    // Set ID
    edge->setId(edgeIDGenerator);
    edgeIDGenerator++;

    // Out edge for source node
    edge->source = source;
    source->outEdges.push_back(edge);

    // In edge for target node
    edge->target = target;
    target->inEdges.push_back(edge);

    edge->setEdgeProb(edgeProb);

    // Mark the graph modified.
    lastModifiedTraversalNumber = traversalNumber;
}


void ControlFlowGraph::removeEdge(Edge* edge) {
    // Remove out edge from source node
    Node* source = edge->getSourceNode();
    Edges& outEdges = source->outEdges;
    outEdges.erase(std::remove(outEdges.begin(), outEdges.end(), edge));

    // Remove in edge from target node
    Node* target = edge->getTargetNode();
    Edges& inEdges = target->inEdges;
    inEdges.erase(std::remove(inEdges.begin(), inEdges.end(), edge));

    // Mark the graph modified.
    lastModifiedTraversalNumber = traversalNumber;
    lastEdgeRemovalTraversalNumber = traversalNumber;
}

Edge* ControlFlowGraph::replaceEdgeTarget(Edge* edge, Node* newTarget, bool keepOldBody) {
    Node* source = edge->getSourceNode();
    Node* oldTarget = edge->getTargetNode();
    CFGInst* lastInst = source->getLastInst();

    Edge* newEdge = NULL;
    if (keepOldBody) {
        edge->target = newTarget;
        newTarget->inEdges.push_back(edge);
        Edges& oldInEdges = oldTarget->inEdges;
        oldInEdges.erase(std::remove(oldInEdges.begin(), oldInEdges.end(), edge));
        newEdge = edge;
        // Mark the graph modified.
        lastModifiedTraversalNumber = traversalNumber;
    } else {
        removeEdge(edge);
        newEdge = addEdge(source, newTarget);
    }
    if (lastInst!=NULL) {
        lastInst->updateControlTransferInst(oldTarget, newTarget);
    }
    return newEdge;
}


#define PROFILE_ERROR_ALLOWED   0.000000001
#define ABS(a) (((a) > (0)) ? (a) : -(a))


// Check the profile consistency of the CFG.
// Return true if the profile is consistent. Otherwise, return false.
bool ControlFlowGraph::isEdgeProfileConsistent(bool checkEdgeProbs, bool checkExecCounts, bool doAssertForClient) {
    assert(hasEdgeProfile());
    bool profileIsUptodate= lastProfileUpdateTraversalNumber > getModificationTraversalNum();
#ifndef _DEBUG
    if (profileIsUptodate) {
        return true;
    }
#else
    //do self test in debug version
    bool doAssert = profileIsUptodate || doAssertForClient;
#endif

    const Nodes& postOrdered = getNodesPostOrder();
    for (Nodes::const_iterator it = postOrdered.begin(), end = postOrdered.end(); it!=end; ++it) {
        Node* node = *it;
        if (checkEdgeProbs) {
            const Edges& outEdges = node->getOutEdges();
            if (!outEdges.empty()) {
                double probSum = 0;    
                for (Edges::const_iterator ite = outEdges.begin(), ende = outEdges.end(); ite!=ende; ++ite) {
                    Edge* edge = *ite;
                    double prob = edge->getEdgeProb();
                    if (prob <= 0 || prob > 1) {
                        assert(doAssert?false:true);
                        return false;
                    }
                    probSum+=prob;
                }
                if (ABS(probSum-1) > PROFILE_ERROR_ALLOWED) {
                    assert(doAssert?false:true);
                    return false;
                }
            }
        }
        if (checkExecCounts) {
            const Edges& inEdges = node->getInEdges();
            bool hasInfiniteLoops = false;
            if (!inEdges.empty()) {
                double freqSum = 0;
                for (Edges::const_iterator ite = inEdges.begin(), ende = inEdges.end(); ite!=ende; ++ite) {
                    Edge* edge = *ite;
                    Node* sourceNode = edge->getSourceNode();
                    double freq = edge->getEdgeProb() * sourceNode->getExecCount();
                    if (sourceNode->getTraversalNum()!=node->getTraversalNum()) {
                        freq = 0;
                    }
                    if (freq <=0) {
                        assert(doAssert?false:true);
                        return false;
                    }
                    freqSum+=freq;
                }
                if (freqSum <=0 ) {
                    assert(doAssert?false:true);
                    return false;
                }
                double nodeFreq = node->getExecCount();
                if (nodeFreq > 1/PROFILE_ERROR_ALLOWED) {
                    hasInfiniteLoops = true;
                } else if (ABS(nodeFreq / freqSum - 1) >= PROFILE_ERROR_ALLOWED) {
                    assert(doAssert?false:true);
                    return false;
                }
            }
            if (!hasInfiniteLoops && exitNode!=NULL) {
                double exitFreq = exitNode->getExecCount();
                double entryFreq = entryNode->getExecCount();
                bool ok = ABS(exitFreq - entryFreq) < PROFILE_ERROR_ALLOWED * entryFreq;
                if (!ok) {
                    assert(doAssert ? false : true);
                    return false;
                }
            }
        }
    }
    if (!profileIsUptodate && checkEdgeProbs && checkExecCounts) {
        lastProfileUpdateTraversalNumber = getTraversalNum();
    }
    return true;
}   

// this utility splits a node at a particular instruction, leaving the instruction in the
// same node and moving all insts (before inst : splitAfter=false/after inst : splitAfter=true 
// to the newly created node
// returns the new node created
Node* ControlFlowGraph::splitNodeAtInstruction(CFGInst *inst, bool splitAfter, bool keepDispatch, CFGInst* labelInst) {
    Node *node = inst->getNode();
    Node* dispatchNode = keepDispatch ? node->getExceptionEdgeTarget() : NULL;
    Node* newNode =  splitNode(node, true, labelInst);
    if (inst == node->getLastInst()) {
        assert(!splitAfter || (node->getOutDegree() == 1 && node->getUnconditionalEdge()!=NULL)
            || (node->getOutDegree()==2 && node->getExceptionEdgeTarget()!=NULL));
    }  
    
    //keeping dispatch node is useful for extended basis blocks
    if (keepDispatch && dispatchNode!=NULL) {
        assert(node->getExceptionEdgeTarget() == NULL);
        addEdge(node, dispatchNode, 0);
    }

    // now move the instructions
    for (CFGInst *ins = splitAfter ? inst->next() : inst; ins != NULL; ) {
        CFGInst *nextins = ins->next();
        ins->unlink();
        newNode->appendInst(ins);
        ins = nextins;
    } 
    newNode->setExecCount(node->getExecCount());
    node->findTargetEdge(newNode)->setEdgeProb(1.0);
    return newNode;
}

// Splice a new empty block on the CFG edge.
Node* ControlFlowGraph::spliceBlockOnEdge(Edge* edge, CFGInst* inst, bool keepOldEdge) {
    Node*    source = edge->getSourceNode();
    double edgeProb = edge->getEdgeProb();
    double edgeFreq = source->getExecCount()*edgeProb;

    // Split the edge
    Node* split =  splitEdge(edge, inst, keepOldEdge);
    split->setExecCount(edgeFreq);

    // Set the incoming edge probability
    assert(split->getInDegree() == 1);
    split->getInEdges().front()->setEdgeProb(edgeProb);

    // Set the outgoing edge probability
    assert(split->getOutDegree() == 1);
    split->getOutEdges().front()->setEdgeProb(1.0);

    return split;
}


void ControlFlowGraph::splitCriticalEdges(bool includeExceptionEdges, Nodes* newNodes) {
    // go backwards through collection so appending won't hurt us.
    Nodes::reverse_iterator iter = nodes.rbegin(), end = nodes.rend();
    for (int idx = (int)nodes.size(); --idx<=0;) {
        Node* target = nodes[idx];
        // exception edges go to a dispatch node.
        // only look at nodes with multiple in edges.
        if (target->isDispatchNode() || includeExceptionEdges) {
restart:
            if (target->getInDegree() > 1) {
                Edges& inEdges = target->inEdges;
                Edges::iterator iterEdge = inEdges.begin(), endEdge = inEdges.end();
                for (; iterEdge != endEdge; ++iterEdge) {
                    Edge* thisEdge = *iterEdge;
                    Node* source = thisEdge->getSourceNode();
                    if ((source->getOutDegree() > 1) && (includeExceptionEdges || !source->isDispatchNode())) {
                        // it's a critical edge, split it
                        Node* newNode = splitEdge(thisEdge, NULL, false); //TODO: keep old edge?
                        if (newNodes) {
                            newNodes->push_back(newNode);
                        }
                        goto restart;
                    }
                }
            }
        }
    }        
}


bool ControlFlowGraph::isBlockMergeAllowed(Node* source, Node* target, bool allowMergeDispatch) const {
    assert(source->isBlockNode() && target->isBlockNode());
    if (target == returnNode) {
        return false;
    }
    if (source->getUnconditionalEdgeTarget()!=target) {
        return false;
    }
    if (target->getInDegree()!=1 || source->getOutDegree() > 2) {
        return false;
    }

    Node* sourceDispatch = source->getExceptionEdgeTarget();
    Node* targetDispatch = target->getExceptionEdgeTarget();

    //check if there is no problem with header critical insts
    if (source->getLastInst()!=NULL && !source->getLastInst()->isHeaderCriticalInst()) {
        //we can't allow target to have critical insts except label
        CFGInst* inst = target->getFirstInst();
        inst = inst!=NULL?(inst->isLabel() ? inst->next() : inst) : NULL;
        if (inst!=NULL && inst->isHeaderCriticalInst()) {
            return false;
        }
    }

    if (source->getOutDegree() == 2 && sourceDispatch == 0) {
        return false; // 2 uncond edges, e.g. indirect jumps
    }

    if (!allowMergeDispatch) {
        return sourceDispatch==NULL && targetDispatch==NULL;
    }
    
    bool allowMergeByDispatch = sourceDispatch == targetDispatch 
        || (sourceDispatch == unwindNode && targetDispatch == NULL) 
        || (sourceDispatch == NULL && targetDispatch == unwindNode);

    return allowMergeByDispatch;
}


void ControlFlowGraph::mergeBlocks(Node* source, Node* target, bool keepFirst) {
    assert(isBlockMergeAllowed(source, target, true));

    Edge* edge = target->inEdges.front();
    assert(edge->getSourceNode() == source);
    removeEdge(edge);

    if(keepFirst) {
        // Merge second block into first
        moveInstructions(target, source, false);
        moveOutEdges(target, source);
        removeNode(target);
    } else {
        // Merge first block into second
        moveInstructions(source, target, true);
        moveInEdges(source, target);
        removeNode(source);
    }
}

void ControlFlowGraph::mergeAdjacentNodes(bool skipEntry, bool mergeByDispatch) {
    for(U_32 idx = 0; idx < nodes.size(); idx++) {
        Node* node = nodes[idx];
        if (node->isBlockNode() && (!skipEntry || node!=entryNode)) { 
            Node* succ = node->getUnconditionalEdgeTarget();
            if (succ!=NULL && succ->getInDegree() == 1 && !succ->isExitNode()) {
                if (isBlockMergeAllowed(node, succ, mergeByDispatch)){ 
                    mergeBlocks(node, succ);
                    idx--;
                }
            }
        } else if (node->isDispatchNode()) {
            if (node->getOutDegree() == 1 && node->isEmpty()) {
                Node* succ = node->getOutEdges().front()->getTargetNode();
                if (succ->isDispatchNode())  {
                    // This dispatch has no handlers.
                    // Forward edges to this dispatch node to the successor.
                    moveInstructions(node, succ, true);
                    moveInEdges(node, succ);
                    removeNode(nodes.begin() + idx, true);
                    idx--;
                }
            }
        }
    }
}


void ControlFlowGraph::purgeEmptyNodes(bool preserveCriticalEdges, bool removeEmptyCatchBlocks) {
    for(Nodes::iterator it = nodes.begin(),end = nodes.end(); it != end; ++it) {
        Node* node = *it;
        if(node->isBlockNode() && node->isEmpty()) {
            // Preserve entry node
            if(node == getEntryNode() || node == getReturnNode() || (!removeEmptyCatchBlocks  && node->isCatchBlock())) {
                continue;
            }
            // Node must have one unconditional successor if it is empty.
            assert(node->getOutDegree() == 1 || (node->getOutDegree()==2 && node->getExceptionEdge()!=NULL));
            Node* succ = node->getUnconditionalEdgeTarget();
            assert(succ->isBlockNode() || (succ->isExitNode() && getReturnNode() == NULL)); //cfg without special support for return node...
            if(succ == node) {
                // This is an empty infinite loop.
                continue;
            }

            // Preserve this node if it breaks a critical edge if requested.
            bool preserve = false;
            if(preserveCriticalEdges && succ->getInDegree() > 1) {
                // Preserve this block if any predecessors have multiple out edges.
                Edges::const_iterator eiter;
                for(eiter = node->getInEdges().begin(); !preserve && eiter != node->getInEdges().end(); ++eiter) {
                    if((*eiter)->getSourceNode()->getOutDegree() > 1)
                        // This node breaks a critical edge.
                        preserve = true;
                }
            }

            if(!preserve) {
                moveInEdges(node, succ);
                removeNode(it, false);
            }
        }
    }
    nodes.erase(std::remove(nodes.begin(), nodes.end(), (Node*)NULL), nodes.end());
}

void ControlFlowGraph::addNode(Node* node) {
    // Set ID
    node->setId(nodeIDGenerator);
    nodeIDGenerator++;

    // Add node
    nodes.push_back(node);

    // Reset node traversal number
    node->traversalNumber = 0;

    // Mark the graph modified.
    lastModifiedTraversalNumber = traversalNumber;
}


// Splice inlineFG into this CFG.
void ControlFlowGraph::spliceFlowGraphInline(Edge* edge, ControlFlowGraph& inlineFG) {
    assert(!edge->isDispatchEdge() && !edge->isCatchEdge());

    Node* nodeBeforeEntry = edge->getSourceNode();
    Node* nodeAfterReturn = edge->getTargetNode();
    Node* dispatchNode = nodeBeforeEntry->getExceptionEdgeTarget();
    
    Node* inlineEntryNode = inlineFG.getEntryNode();
    Node* inlineReturnNode = inlineFG.getReturnNode();
    Node* inlineUnwindNode = inlineFG.getUnwindNode();
    Node* inlineExitNode = inlineFG.getExitNode();

    bool returnSeen = false;
    bool unwindSeen = false;

   
    // Add nodes to CFG
    assert(&getMemoryManager() == &inlineFG.getMemoryManager());
    const Nodes& inlineNodes = inlineFG.getNodes();
    for(Nodes::const_iterator i = inlineNodes.begin(), end = inlineNodes.end(); i != end; ++i) {
        Node* n = *i;
        if (n != inlineExitNode) {
            addNode(n);
            const Edges& oEdges = n->getOutEdges();
            Edges::const_iterator e;
            for(e = oEdges.begin(); e != oEdges.end(); ++e) {
                setNewEdgeId(*e);
            }
            if (n == inlineReturnNode) {
                returnSeen = true;
            } else if (n == inlineUnwindNode) {
                unwindSeen = true;
            }
        }

    }
    
    // Connect nodes.
    replaceEdgeTarget(edge, inlineEntryNode);
    if(returnSeen) { 
        removeEdge(inlineReturnNode, inlineExitNode);
        addEdge(inlineReturnNode, nodeAfterReturn, 1); 
    }
    if(unwindSeen) {
        removeEdge(inlineUnwindNode, inlineExitNode);
        if (dispatchNode == NULL) {
            dispatchNode = getUnwindNode();
        }
        assert(dispatchNode != NULL);
        addEdge(inlineUnwindNode, dispatchNode, 1);
    }
}


void ControlFlowGraph::spliceFlowGraphInline(CFGInst* instAfter, ControlFlowGraph& inlineFG) {
    Node* node = instAfter->getNode();
    Edge* edgeToInlined = NULL;
    if (node->getLastInst() == instAfter) {
        edgeToInlined =  node->getUnconditionalEdge();
    } else {//WARN: no label inst created -> possible problems if method is used in HLO
        Node* newBlock = splitNodeAtInstruction(instAfter, true, false, NULL);
        assert(newBlock->getInDegree() == 1);
        edgeToInlined = newBlock->getInEdges().front();
    }
    assert(edgeToInlined!=NULL);
    spliceFlowGraphInline(edgeToInlined, inlineFG);
 }


void ControlFlowGraph::moveInEdges(Node* oldNode, Node* newNode) {
    assert(oldNode != newNode);
    assert(oldNode->getKind() == newNode->getKind() || (getReturnNode()==NULL && newNode->isExitNode()));
    Edges& oldIns = oldNode->inEdges;
    Edges& newIns = newNode->inEdges;
    newIns.insert(newIns.begin(), oldIns.begin(), oldIns.end());
    oldIns.clear();
    // Reset edge pointers and update branch instructions.
    resetInEdges(newNode);
    assert(oldNode->getInDegree() == 0);

    // Mark the graph modified.
    lastModifiedTraversalNumber = traversalNumber;
}

void
ControlFlowGraph::moveOutEdges(Node* oldNode, Node* newNode) {
    assert(oldNode->getKind() == newNode->getKind());
    Edges& oldOuts = oldNode->outEdges;
    Edges& newOuts = newNode->outEdges;
    newOuts.insert(newOuts.end(), oldOuts.begin(), oldOuts.end());
    oldOuts.clear();
    resetOutEdges(newNode);
    assert(oldNode->getOutDegree() == 0);

    // Mark the graph modified.
    lastModifiedTraversalNumber = traversalNumber;
}


void ControlFlowGraph::resetInEdges(Node* node) {
    Edges& edges = node->inEdges;
    for(int i=(int)edges.size(); --i>=0;) {
        Edge* edge = edges[i];
        // The old successor; node is the new successor
        Node* old = edge->getTargetNode();
        if(old != node) {
            Node* pred = edge->getSourceNode();
            // Check if another edge already goes to node.  .
            bool redundant = (pred->findTargetEdge(node) != NULL);
            // Set this edge to point to node.  Note, we do this even if the
            // edge is to be deleted.  removeEdge only works if the edge
            // is well-formed.
            edge->target = node;
            // Update control transfer instruction in source.
            CFGInst* lastInst = pred->getLastInst();
            if(pred->isBlockNode() && lastInst!=NULL) {
                lastInst->updateControlTransferInst(old, node);
            }
            if(redundant) {
                // Edge is redundant - eliminate.
                if(pred->getOutDegree() == 2 || (pred->getOutDegree()==3 && pred->getExceptionEdge()!=NULL)) {
                    // Pred already has edge to node and succ, and no other successors.  
                    // We can eliminate the branch and the edge to succ.
                    // Another case is branch+exception for extended form
                    if(pred->isBlockNode()) {
                        lastInst->removeRedundantBranch();
                    }
                }
                removeEdge(edge);
            }
        }
    }
}

void ControlFlowGraph::resetOutEdges(Node* node) {
    Edges& edges = node->outEdges;
    for(int i=(int)edges.size(); --i>=0;) {
        Edge* edge = edges[i];
        // The old predecessor; node is the new predecessor
        Node* old = edge->getSourceNode();
        if(old != node) {
            Node* succ = edge->getTargetNode();
            // Check if another edge already comes from node.
            bool redundant = (succ->findSourceEdge(node) != NULL);
            // Set this edge to point to node.  Note, we do this even if the
            // edge is to be deleted.  removeEdge only works if the edge
            // is well-formed.
            edge->source = node;
            if(redundant) {
                // Edge is redundant - eliminate.
                removeEdge(edge);
            }
        }
    }
}

Node* ControlFlowGraph::splitNode(Node* node, bool newBlockAtEnd, CFGInst* inst) {
    assert(node->isBlockNode());
    Node* newNode = createBlockNode(inst);
    if(newBlockAtEnd) {
        // move out edges
        moveOutEdges(node, newNode);
        addEdge(node, newNode);
    } else { // new block at beginning
        // move in edges
        moveInEdges(node, newNode);
        addEdge(newNode, node);
    }
    return newNode;
}

Node* ControlFlowGraph::splitEdge(Edge *edge, CFGInst* inst, bool keepOldEdge) {
    Node* target = edge->getTargetNode();
    Node* newNode = createBlockNode(inst);
    if (inst!=NULL && target->getFirstInst()!=NULL) {
        inst->setBCOffset(target->getFirstInst()->getBCOffset());
    }

    replaceEdgeTarget(edge, newNode, keepOldEdge);
    addEdge(newNode, target);

    return newNode;
}

void ControlFlowGraph::moveInstructions(Node* fromNode, Node* toNode, bool prepend) {
    CFGInst* to = prepend ? toNode->getFirstInst() : toNode->getLastInst();
    CFGInst *inst = fromNode->getFirstInst();
    if (inst!=NULL && inst->isLabel()) { //skip block label if exists
        inst = inst->next();
    }
    for (; inst != NULL;  ) {
        CFGInst *next = inst->next();
        inst->unlink();
        if (to == NULL) {
            if (prepend) {
                toNode->prependInst(inst);
            } else {
                toNode->appendInst(inst);
            }
        } else {
            inst->insertAfter(to);
        }
        to = inst;
        assert(prepend || to == toNode->getLastInst());
        inst = next;
    }
}

class CountFreqsAlgorithm {
public:
    CountFreqsAlgorithm(MemoryManager& _mm, ControlFlowGraph* _fg)  :
        mm(_mm), fg(_fg), loopTree(fg->getLoopTree()), 
        useCyclicFreqs(false), cyclicFreqs(NULL), exitEdges(mm)
    {
        if (!loopTree->isValid()) {
            loopTree->rebuild(false);
        }
        U_32 nNodes = fg->getNodeCount();
        cyclicFreqs = new (mm) double[nNodes];
        std::fill(cyclicFreqs, cyclicFreqs + nNodes, 1);
    }

    void estimate() {
        smoothLinearFrequencies();
        LoopNode* topLevelLoops = (LoopNode*)loopTree->getRoot();
        if (topLevelLoops->getChild()!=NULL) { //if there are loops in method
            useCyclicFreqs = true;
            for (LoopNode* loopHead = topLevelLoops->getChild(); loopHead!=NULL; loopHead = loopHead->getSiblings()) {
                estimateCyclicFrequencies(loopHead);
            }
            smoothLinearFrequencies();
        }
    }

    
    void smoothLinearFrequencies() {
        const Nodes& nodes = fg->getNodesPostOrder();
        for (Nodes::const_reverse_iterator it = nodes.rbegin(), end = nodes.rend(); it!=end; ++it) {
            Node* node = *it;
            const Edges& inEdges = node->getInEdges();
            if (inEdges.empty()) { 
                //node is entry, do nothing
                assert (node == fg->getEntryNode());
                continue;
            }
            double freq = 0.0;
            for(Edges::const_iterator it = inEdges.begin(), itEnd = inEdges.end(); it!=itEnd; it++) {
                Edge* edge = *it;
                if (loopTree->isBackEdge(edge)) { 
                    continue; //only linear freq estimation
                }
                Node* fromNode = edge->getSourceNode();
                if (fromNode->getTraversalNum()!=node->getTraversalNum()) {
                    continue;//unreachable source node
                }
                double fromFreq = fromNode->getExecCount();
                freq += fromFreq * edge->getEdgeProb();
            }
            if (useCyclicFreqs && loopTree->isLoopHeader(node)) {
                freq *= cyclicFreqs[node->getDfNum()];
            }
            node->setExecCount(freq);
        }
    }
    
    void estimateCyclicFrequencies(LoopNode* loopHead) {
        //process all child loops first
        bool hasChildLoop = loopHead->getChild()!=NULL;
        if (hasChildLoop) {
            for (LoopNode* childHead = loopHead->getChild(); childHead!=NULL; childHead = childHead->getSiblings()) {
                estimateCyclicFrequencies(childHead);
            }
        }
        findLoopExits(loopHead);
        if (hasChildLoop) {
            smoothLinearFrequencies();
        }
        Node* cfgLoopHead = loopHead->getHeader();
        double inFlow = cfgLoopHead->getExecCount(); //node has linear freq here
        double exitsFlow = 0;
        //sum all exits flow
        for (Edges::const_iterator it = exitEdges.begin(), end = exitEdges.end(); it!=end; ++it) {
            Edge* edge = *it;
            Node* fromNode = edge->getSourceNode();
            exitsFlow += edge->getEdgeProb() * fromNode->getExecCount();
        }
        // if loop will make multiple iteration exitsFlow becomes equals to inFlow
        double loopCycles = inFlow / exitsFlow;
        if (loopCycles < 1) {
            assert(ABS(inFlow-exitsFlow) < PROFILE_ERROR_ALLOWED);
            loopCycles = 1;
        }
        cyclicFreqs[cfgLoopHead->getDfNum()] = loopCycles;
    }

    void findLoopExits(LoopNode* loop) {
        exitEdges.clear();
        const Nodes& nodes = loop->getNodesInLoop();
        for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) {
            Node* node = *it;
            const Edges& outEdges = node->getOutEdges();
            for(Edges::const_iterator eit = outEdges.begin(), eend = outEdges.end(); eit!=eend; ++eit) {
                Edge* edge = *eit;
                if (loop->isLoopExit(edge)) {
                    exitEdges.push_back(edge);
                }
            }
        }
    }
private:
    MemoryManager& mm;
    ControlFlowGraph* fg;
    LoopTree* loopTree;
    bool useCyclicFreqs;
    double* cyclicFreqs;
    Edges exitEdges;
};

//count node exec count from probs
void ControlFlowGraph::smoothEdgeProfile() {
    assert(isEdgeProfileConsistent(true, false, true));
    if (isEdgeProfileConsistent(true, true)) {
        return;
    }
    assert(entryNode->getExecCount()!=0);
    CountFreqsAlgorithm c(mm, this);
    c.estimate();
    lastProfileUpdateTraversalNumber = traversalNumber;
    assert(isEdgeProfileConsistent(true, true, true));
}

//////////////////////////////////////////////////////////////////////////
/// CFGInst methods

CFGInst* CFGInst::next() const {
    CFGInst* next = (CFGInst*)getNext();
    return  (node!=NULL && next == node->instsHead) ? NULL : next;
}

CFGInst* CFGInst::prev() const {
    CFGInst* prev = (CFGInst*)getPrev(); 
    return (node!=NULL && prev == node->instsHead) ? NULL : prev;
}

void CFGInst::insertBefore(CFGInst* inst) {
    assert(node == NULL);
    CFGInst* nextInst = next();
    unlink();
    Node* newNode = inst->getNode();
    if (newNode!= NULL) {
        newNode->insertInst((CFGInst*)inst->getPrev(), this);
    } else {
        ((Dlink*)this)->insertBefore(inst);
    }
    if (nextInst!=this) {
        nextInst->insertBefore(inst);
    }
}

void CFGInst::insertAfter(CFGInst* inst) { 
    assert(node == NULL);
    CFGInst* nextInst = next();
    unlink();
    Node* newNode = inst->getNode();
    if (newNode!=NULL) {
        newNode->insertInst(inst, this);
    } else {
        ((Dlink*)this)->insertAfter(inst);
    }
    if (nextInst!=this) {
        nextInst->insertAfter(this);
    }
}

} //namespace