/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

/**
 * @author Intel, Pavel A. Ozhdikhin
 *
 */

#include "Opcode.h"
#include "Type.h"
#include "FlowGraph.h"
#include "Dominator.h"
#include "Stack.h"
#include "IRBuilder.h"
#include "irmanager.h"
#include "Log.h"
#include "XTimer.h"
#include "StaticProfiler.h"
#include "escapeanalyzer.h"
#include "deadcodeeliminator.h"
#include "TranslatorIntfc.h"
#include "LoopTree.h"
#include "inliner.h"

#include <stdlib.h>
#include <string.h>

namespace Jitrino {

void         
FlowGraph::foldBranch(ControlFlowGraph& fg, BranchInst* br, bool isTaken)
{
	Node* block = br->getNode();
	assert(block->getOutDegree() == 2);
	
    fg.removeEdge(block->getOutEdge(isTaken ? Edge::Kind_False : Edge::Kind_True));
    br->unlink();
}

void         
FlowGraph::foldSwitch(ControlFlowGraph& fg, SwitchInst* sw, U_32 index)
{
    Node* block = sw->getNode();
    assert(sw == block->getLastInst());
    LabelInst* target;
    if(index < sw->getNumTargets())
        target = sw->getTarget(index);
    else
        target = sw->getDefaultTarget();

    while (!block->getOutEdges().empty()) {
        fg.removeEdge(block->getOutEdges().back());
    }
    sw->unlink();
    fg.addEdge(block, target->getNode(), 1.0);
}


void         
FlowGraph::eliminateCheck(ControlFlowGraph& fg, Node* block, Inst* check, bool alwaysThrows)
{
    assert(check == (Inst*)block->getLastInst() &&  check->getOperation().canThrow());
    Edge* edge = NULL;
    if (alwaysThrows) {
#ifndef NDEBUG
        Inst *prevInst = check->getPrevInst();
        assert(prevInst->isThrow());
#endif
        edge = block->getUnconditionalEdge();
    } else {
        edge = block->getExceptionEdge();
    }
    assert(edge != NULL);
    fg.removeEdge(edge);
    check->unlink();
}


Node* 
FlowGraph::tailDuplicate(IRManager& irm, Node* pred, Node* tail, DefUseBuilder& defUses) {
    MemoryManager mm("FlowGraph::tailDuplicate.mm");
    ControlFlowGraph& fg = irm.getFlowGraph();

    // Set region containing only node.
    StlBitVector region(mm, fg.getMaxNodeId()*2);
    region.setBit(tail->getId());

    // Make copy.
    Node* copy = duplicateRegion(irm, tail, region, defUses);

    // Specialize for pred.
    Edge* edge = fg.replaceEdgeTarget(pred->findTargetEdge(tail), copy, true);
    copy->setExecCount(pred->getExecCount()*edge->getEdgeProb());
    if(copy->getExecCount() < tail->getExecCount())  {
        tail->setExecCount(tail->getExecCount() - copy->getExecCount());
    } else {
        tail->setExecCount(0);
    }
    return copy;
}

Node* FlowGraph::duplicateNode(IRManager& irm, Node *source, Node *before, OpndRenameTable *renameTable) {
    Node *newblock;
    LabelInst *first = (LabelInst*)source->getFirstInst();
    if(Log::isEnabled()) {
        first->print(Log::out()); Log::out() << std::endl;
    }
    InstFactory& instFactory = irm.getInstFactory();
    OpndManager& opndManager = irm.getOpndManager();
    ControlFlowGraph& fg = irm.getFlowGraph();
    LabelInst* l = (LabelInst*)instFactory.clone(first,opndManager,renameTable);
    newblock = fg.createNode(source->getKind(), l);
    l->setState(first->getState());

    // go throw the 'entry' instructions and duplicate them (renaming whenever possible)
    for (Inst *inst = first->getNextInst(); inst != NULL; inst = inst->getNextInst()) {
        if(Log::isEnabled()) {
            Log::out() << "DUPLICATE ";
            Log::out().flush();
            inst->print(Log::out()); Log::out() << "\n";
            Log::out().flush();
        }

        Inst* newInst = instFactory.clone(inst,opndManager,renameTable);
        newblock->appendInst(newInst);
        if(Log::isEnabled()) {
            Log::out() << "          ";
            Log::out() << (I_32)inst->getNumSrcOperands();
            Log::out() << " " << (I_32)inst->getOpcode() << " ";
            newInst->print(Log::out());
            Log::out() << "\n";
            Log::out().flush();
        }
    }
    return newblock;
}


Node* FlowGraph::duplicateNode(IRManager& irm, Node *node, StlBitVector* nodesInRegion, 
                           DefUseBuilder* defUses, OpndRenameTable* opndRenameTable,
                           NodeRenameTable* reverseNodeRenameTable) 
{
    if(Log::isEnabled()) {
        Log::out() << "DUPLICATE NODE " << std::endl;
        FlowGraph::print(Log::out(), node);
    }

    InstFactory& instFactory = irm.getInstFactory();
    OpndManager& opndManager = irm.getOpndManager();
    ControlFlowGraph& fg = irm.getFlowGraph();

    Node *newNode;
    LabelInst *first = (LabelInst*)node->getFirstInst();
    LabelInst* l = (LabelInst*)instFactory.clone(first,opndManager,opndRenameTable);
    newNode  = fg.createNode(node->getKind(), l);
    l->setState(first->getState());
    reverseNodeRenameTable->setMapping(newNode, node);

    // Copy edges
    const Edges& outEdges = node->getOutEdges();
    Edges::const_iterator eiter;
    for(eiter = outEdges.begin(); eiter != outEdges.end(); ++eiter) {
        Edge* edge = *eiter;
        Node* succ = edge->getTargetNode();
        Edge* newEdge = fg.addEdge(newNode, succ);
        newEdge->setEdgeProb(edge->getEdgeProb());
    }    

    Node* stBlock = NULL;

    // go throw the 'entry' instructions and duplicate them (renaming whenever possible)
    for (Inst *inst = first->getNextInst(); inst != NULL; inst = inst->getNextInst()) {
        if(Log::isEnabled()) {
            Log::out() << "DUPLICATE ";
            Log::out().flush();
            inst->print(Log::out()); Log::out() << "\n";
            Log::out().flush();
        }

        // Create clone inst, add to new node, and update defuse links.
        Inst* newInst = instFactory.clone(inst,opndManager,opndRenameTable);
        
        // Special care required for SSA operands.
        Opnd* dst = inst->getDst();
        if(dst->isSsaOpnd()) {
            // Determine if dst should be promoted to a var.
            Opnd* var = NULL;
            SsaVarOpnd* srcVar1 = NULL;
            SsaVarOpnd* srcVar2 = NULL;
            DefUseLink* duLink = NULL;

            for(duLink = defUses->getDefUseLinks(inst); duLink != NULL; duLink = duLink->getNext()) {
                int index = duLink->getSrcIndex();
                Inst* useInst = duLink->getUseInst();
                Node* useNode = useInst->getNode();
                assert(useNode != NULL);
                
                if(Log::isEnabled()) {
                    Log::out() << "Examine use: ";
                    useInst->print(Log::out());
                    Log::out() << std::endl;
                }
                
                // No special actions for nodes to be clonned.
                if (nodesInRegion->getBit(useNode->getId())) continue;

                // Handle variables.
                if (dst->isSsaVarOpnd()) {
                    defUses->removeDefUse(inst, useInst, index);
                    // Handle cyclic dependence.
                    if (reverseNodeRenameTable->getMapping(useNode) != NULL) {
                        // There is already phi insturction.
                        // Just update source operand.
                        useInst->setSrc(index, newInst->getDst());
                        defUses->addDefUse(newInst, useInst, index);
                        continue;
                    }
                    // Insert phi instruction.
                    srcVar1 = inst->getDst()->asSsaVarOpnd();
                    srcVar2 = newInst->getDst()->asSsaVarOpnd();
                    StlBitVector visitedNodes = StlBitVector(irm.getMemoryManager(), fg.getMaxNodeId(), false); 
                    Inst* phiInst = insertPhi(irm, nodesInRegion, reverseNodeRenameTable,
                        visitedNodes, useNode, defUses, srcVar1, srcVar2);
                    useInst->setSrc(index, phiInst->getDst());
                    defUses->addDefUse(phiInst, useInst, index);                    
                } else {
                    assert(!dst->isVarOpnd() && !dst->isSsaVarOpnd());
                    // Need to promote dst to variable.
                    if(Log::isEnabled()) {
                        Log::out() << "Patch use: ";
                        useInst->print(Log::out());
                        Log::out() << std::endl;
                    }
                    Inst* patchdef = NULL;
                    ConstInst* ci = inst->asConstInst();
                    if(ci != NULL) {
                        MemoryManager mm("FlowGraph::duplicateNode.mm");
                        OpndRenameTable table(mm,1);
                        patchdef = instFactory.clone(ci, opndManager, &table)->asConstInst();
                        assert(patchdef != NULL);
                    } else {
                        if(var == NULL) {
                            var = opndManager.createVarOpnd(dst->getType(), false);
                            if (irm.getInSsa()) {
                                var = opndManager.createSsaVarOpnd(var->asVarOpnd());
                            }

                            Inst* stVar = irm.getInSsa() ? instFactory.makeStVar(var->asSsaVarOpnd(), dst)
                                : instFactory.makeStVar(var->asVarOpnd(), dst);
                            if(inst->getOperation().canThrow()) {
                                LabelInst* lblInst = instFactory.makeLabel();
                                assert(inst->getBCOffset()!=ILLEGAL_BC_MAPPING_VALUE);
                                lblInst->setBCOffset(inst->getBCOffset());
                                stBlock = fg.createBlockNode(lblInst);
                                stBlock->appendInst(stVar);
                                Node* succ =  node->getUnconditionalEdge()->getTargetNode();
                                Edge* succEdge = node->findTargetEdge(succ);
                                stBlock->setExecCount(node->getExecCount()*succEdge->getEdgeProb());
                                fg.replaceEdgeTarget(succEdge, stBlock, true);
                                fg.replaceEdgeTarget(newNode->findTargetEdge(succ), stBlock, true);
                                fg.addEdge(stBlock, succ)->setEdgeProb(1.0);
                                defUses->addUses(stVar);
                                nodesInRegion->resize(stBlock->getId()+1);
                                nodesInRegion->setBit(stBlock->getId());
                            } else {
                                stVar->insertAfter(inst);
                                defUses->addUses(stVar);
                            }
                        }

                        Opnd* newUse = opndManager.createSsaTmpOpnd(dst->getType());
                        patchdef = irm.getInSsa() ?  instFactory.makeLdVar(newUse, var->asSsaVarOpnd())
                            : instFactory.makeLdVar(newUse, var->asVarOpnd());
                    }

                    //
                    // Patch useInst to load from var.
                    //
                    patchdef->insertBefore(useInst);
                    defUses->addUses(patchdef);
                    useInst->setSrc(index, patchdef->getDst());

                    //
                    // Update def-use chains.
                    //
                    defUses->removeDefUse(inst, useInst, index);
                    defUses->addDefUse(patchdef, useInst, index);
                }
            }
        }
        
        newNode->appendInst(newInst);        
        defUses->addUses(newInst);
    }
    if(Log::isEnabled()) {
        FlowGraph::print(Log::out(), newNode);
        Log::out() << "---------------" << std::endl;
    }
    return newNode;
}

Inst* FlowGraph::insertPhi(IRManager& irm, StlBitVector* nodesInRegion,
                           NodeRenameTable* reverseNodeRenameTable,
                           StlBitVector& visitedNodes,
                           Node* useNode, DefUseBuilder* defUses,
                           SsaVarOpnd* srcVar1, SsaVarOpnd* srcVar2) {
    Inst* phiInst = NULL;
    std::set<SsaVarOpnd*> phiOpnds;
    
    // Check if we already visited this node.
    if (visitedNodes.getBit(useNode->getId())) {
        return NULL;
    }
    
    // Mark node as visited.
    visitedNodes.setBit(useNode->getId(), true);
    
    // Find in values throug all eges.
    const Edges& inEdges = useNode->getInEdges();
    for (Edges::const_iterator it = inEdges.begin(), end = inEdges.end(); it != end; it++) {
        Edge* inEdge = *it;
        if (nodesInRegion->getBit(inEdge->getSourceNode()->getId())) {
            phiOpnds.insert(phiOpnds.end(), srcVar1);
            phiOpnds.insert(phiOpnds.end(), srcVar2);            
        } else if (!reverseNodeRenameTable->getMapping(inEdge->getSourceNode())){
            Inst* phi = insertPhi(irm, nodesInRegion, reverseNodeRenameTable,
                visitedNodes, inEdge->getSourceNode(), defUses, srcVar1, srcVar2);
            if (phi != NULL) {
                phiOpnds.insert(phiOpnds.end(), phi->getDst()->asSsaVarOpnd());
            }
        }
    }
    
    // Merge input values.
    if (phiOpnds.size() == 1) {
        phiInst = (*phiOpnds.begin())->getInst();
    } else if (phiOpnds.size() > 1) {
        Opnd** opnds = (Opnd**)irm.getMemoryManager().alloc(sizeof(Opnd*) * phiOpnds.size()); 
        std::copy(phiOpnds.begin(), phiOpnds.end(), opnds);
        phiInst = findPhi(useNode, opnds, phiOpnds.size());
        if (phiInst == NULL) {
            SsaVarOpnd* dst = irm.getOpndManager().createSsaVarOpnd(srcVar1->getVar());
            phiInst = irm.getInstFactory().makePhi(dst, phiOpnds.size(), opnds);
            useNode->prependInst(phiInst);
            defUses->addUses(phiInst);
        }
    }
    return phiInst;
}

Inst* FlowGraph::findPhi(Node* node, Opnd** opnds, int opndsCount) {
    
    for (Inst* inst = (Inst*)node->getFirstInst(); inst != NULL; inst = inst->getNextInst()) {        
        if (inst->getOpcode() == Op_Phi && inst->getNumSrcOperands() == (U_32)opndsCount) {
            for (int i = 0; i < opndsCount; i++) {
                if (inst->getSrc(i) != opnds[i]) {
                    break;
                }
                return inst;
            }
        }
    }
    return NULL;
}

Node* FlowGraph::_duplicateRegion(IRManager& irm, Node* node, Node* entry,
                              StlBitVector& nodesInRegion,
                              DefUseBuilder* defUses,
                              NodeRenameTable* nodeRenameTable,
                              NodeRenameTable* reverseNodeRenameTable,
                              OpndRenameTable* opndRenameTable) {
    assert(nodesInRegion.getBit(node->getId()));
    Node* newNode = nodeRenameTable->getMapping(node);
    if(newNode != NULL)
        return newNode;

    newNode = duplicateNode(irm, node, &nodesInRegion, defUses, opndRenameTable, reverseNodeRenameTable);
    nodeRenameTable->setMapping(node, newNode);

    ControlFlowGraph& fg = irm.getFlowGraph();
    const Edges& outEdges = node->getOutEdges();
    Edges::const_iterator eiter;
    for(eiter = outEdges.begin(); eiter != outEdges.end(); ++eiter) {
        Edge* edge = *eiter;
        Node* succ = edge->getTargetNode();
        if(nodesInRegion.getBit(succ->getId())) {
            Node* newSucc = nodeRenameTable->getMapping(succ); 
            if (newSucc == NULL) {
                newSucc = _duplicateRegion(irm, succ, entry, nodesInRegion,
                    defUses, nodeRenameTable, reverseNodeRenameTable, opndRenameTable);
                assert(newSucc != NULL);
            }
            fg.replaceEdgeTarget(newNode->findTargetEdge(succ), newSucc, true);
        }
    }    

    return newNode;
}


Node* FlowGraph::duplicateRegion(IRManager& irm, Node* entry,
                                 StlBitVector& nodesInRegion,
                                 DefUseBuilder& defUses,
                                 NodeRenameTable& nodeRenameTable,                                 
                                 OpndRenameTable& opndRenameTable,
                                 double newEntryFreq) {
    NodeRenameTable* reverseNodeRenameTable = new (irm.getMemoryManager()) 
        NodeRenameTable(irm.getMemoryManager(), nodesInRegion.size());     
    Node* newEntry = _duplicateRegion(irm, entry, entry, nodesInRegion,
        &defUses, &nodeRenameTable, reverseNodeRenameTable, &opndRenameTable);
    if(newEntryFreq == 0) {
        return newEntry;
    }
    double scale = newEntryFreq / entry->getExecCount();
    assert(scale >=0 && scale <= 1);
    NodeRenameTable::Iter iter(&nodeRenameTable);
    Node* oldNode = NULL;
    Node* newNode = NULL;
    while(iter.getNextElem(oldNode, newNode)) {
        newNode->setExecCount(oldNode->getExecCount()*scale);
        oldNode->setExecCount(oldNode->getExecCount()*(1-scale));
    }
    return newEntry;
}


Node* FlowGraph::duplicateRegion(IRManager& irm, Node* entry, StlBitVector& nodesInRegion, DefUseBuilder& defUses, double newEntryFreq) {
    MemoryManager dupMemManager("FlowGraph::duplicateRegion.dupMemManager");
    // prepare the hashtable for the operand rename translation
    OpndRenameTable    *opndRenameTable = new (dupMemManager) OpndRenameTable(dupMemManager, nodesInRegion.size());
    NodeRenameTable *nodeRenameTable = new (dupMemManager) NodeRenameTable(dupMemManager, nodesInRegion.size());
    return duplicateRegion(irm, entry, nodesInRegion, defUses, *nodeRenameTable, *opndRenameTable, newEntryFreq);
}

void FlowGraph::renameOperandsInNode(Node *node, OpndRenameTable *renameTable) {
    Inst *first = (Inst*)node->getFirstInst();
    for (Inst *inst = first->getNextInst(); inst != NULL; inst = inst->getNextInst()) {
        U_32 n = inst->getNumSrcOperands();
        for(U_32 i = 0; i < n; ++i) {
            Opnd* src = inst->getSrc(i);
            Opnd* newsrc = renameTable->getMapping(src);
            if(newsrc != NULL)
                inst->setSrc(i, newsrc);
        }
    }
}

//
// used to find 'saveret' that starts the node
//     'labelinst' and 'stvar' are skipped
//
static Inst* findSaveRet(Node* node) {
    assert(node);
    Inst* first = (Inst*)node->getFirstInst();
    assert(first->getOpcode() == Op_Label);
    Inst* i;
    for ( i = first->getNextInst(); i != NULL; i = i->getNextInst() ) {
        Opcode opc = i->getOpcode();
        if ( opc == Op_SaveRet ) {
            return i;
        }else if ( opc != Op_LdVar ) {
            return NULL;
        }
    }
    return NULL;
}

void static findNodesInRegion(Node* entry, Node* end, StlBitVector& nodesInRegion) {
    if(Log::isEnabled()) {
        Log::out() << "Find nodes in region (entry = ";
        FlowGraph::printLabel(Log::out(), entry);
        Log::out() << ", exit = ";
        FlowGraph::printLabel(Log::out(), end);
        Log::out() << ")" << std::endl;
    }

    // Return if visited and mark.
    if(nodesInRegion.setBit(end->getId()))
        return;

    if(end != entry) {
        const Edges& inEdges = end->getInEdges();
        // Must not be method entry.
        assert(!inEdges.empty());
        Edges::const_iterator eiter;
        for(eiter = inEdges.begin(); eiter != inEdges.end(); ++eiter) {
            Edge* edge = *eiter;
            findNodesInRegion(entry, edge->getSourceNode(), nodesInRegion);
        }
    }
    assert(nodesInRegion.getBit(entry->getId()));
}


static bool inlineJSR(IRManager* irManager, Node *block, DefUseBuilder& defUses, JsrEntryInstToRetInstMap& entryMap) {
    // Inline the JSR call at the end of block.
    Inst* last = (Inst*)block->getLastInst();
    assert(last->isJSR());
    BranchInst* jsrInst   = (BranchInst*) last;

    //
    // Process entry of JSR.
    //
    Node* entryJSR  = jsrInst->getTargetLabel()->getNode();
    Inst *saveReturn = findSaveRet(entryJSR);
    assert(saveReturn);
    //
    // if JSR 'returns' via at least one RET
    // then
    //     'stvar' follows 'saveret' and stores return info into the local var
    //     retVar (the stored operand) is non-NULL
    // else
    //     no 'stvar' can follow 'saveret' (because it is unused)
    //     retVar is NULL
    Inst *stVar = saveReturn->getNextInst();
    Opnd *retVar = NULL;
    if ( stVar && 
         stVar->isStVar() && 
         (stVar->getSrc(0) == saveReturn->getDst()) ) {
        retVar = stVar->getDst();
    }

    //
    // Find return node for this invocation.
    //
    Node* retTarget = NULL;
    const Edges& outEdges = block->getOutEdges();
    Edges::const_iterator eiter;
    for(eiter = outEdges.begin(); eiter != outEdges.end(); ++eiter) {
        Edge* edge = *eiter;
        Node *node = edge->getTargetNode(); 
        if (node != entryJSR && !node->isDispatchNode()) {
            retTarget = node;
            break;
        }
    }

    if(Log::isEnabled()) {
        Log::out() << "INLINE JSR into ";
        FlowGraph::printLabel(Log::out(), block);
        Log::out() << ":" << std::endl;
        FlowGraph::print(Log::out(), entryJSR);
    }

    ControlFlowGraph& fg = irManager->getFlowGraph();

    //
    // entryMap is a mapping [stVar -> ret inst]
    //
    // In some cases retNode exists, but is unreachable
    // Let's check this
    // if retNodeIsUnrichable==true
    // then JSR never returns.  Convert to jmp
    bool retNodeIsUnreachable = true;
    if (entryMap.find(stVar) != entryMap.end()) {
        JsrEntryCIterRange jsr_range = entryMap.equal_range(stVar);
        JsrEntryInstToRetInstMap::const_iterator i;
        for(i = jsr_range.first; i != jsr_range.second; ++i) {
            assert(i->first->getNode() == entryJSR);
            Node* retNode = i->second->getNode();
            UNUSED Inst* ret = (Inst*)retNode->getLastInst();
            assert(ret->isRet());
            assert(ret->getSrc(0) == retVar);

            const Edges& inEdges = retNode->getInEdges();
            if (!inEdges.empty()) {
                retNodeIsUnreachable = false;
                break;
            }
        }
    }

    if(retNodeIsUnreachable == true || retVar == NULL || (entryMap.find(stVar) == entryMap.end())) {
        //
        // JSR never returns.  Convert to jmp.
        //
        saveReturn->unlink();
        if(retVar != NULL) {
            irManager->getOpndManager().deleteVar((VarOpnd*)retVar);
        }

        const Edges& inEdges = entryJSR->getInEdges();
        for(eiter = inEdges.begin(); eiter != inEdges.end();) {
            Edge* edge = *eiter;
            ++eiter;
            Node *node = edge->getSourceNode();
            Inst* last = (Inst*)node->getLastInst();
            if (last->isJSR()) {
	           last->unlink();
            }
            if (node->getOutDegree() == 2) {
	            Node* t1 = node->getOutEdges().front()->getTargetNode();
	            Node* t2 = node->getOutEdges().back()->getTargetNode();
	            if(t1 == entryJSR) {
	                fg.removeEdge(node, t2);
	            } else {
	                assert(t2 == entryJSR);
	                fg.removeEdge(node, t1);
	            }
            }
        }
    } else if (entryJSR->hasOnlyOnePredEdge()) {
        // 
        // Inline the JSR in place - no duplication needed.
        //
        fg.removeEdge(block,retTarget);
        jsrInst->unlink();

        JsrEntryCIterRange jsr_range = entryMap.equal_range(stVar);
        JsrEntryInstToRetInstMap::const_iterator i;
        for(i = jsr_range.first; i != jsr_range.second; ++i) {
            assert(i->first->getNode() == entryJSR);
            Node* retNode = i->second->getNode();
            Inst* ret = (Inst*)retNode->getLastInst();
            assert(ret->isRet());
            assert(ret->getSrc(0) == retVar);
            ret->unlink();
            fg.addEdge(retNode, retTarget);
        }
    } else {
        //
        // Duplicate and inline the JSR.
        //
        MemoryManager inlineManager("FlowGraph::inlineJSR.inlineManager"); 

        // Find the nodes in the JSR.
        StlBitVector nodesInJSR(inlineManager, fg.getMaxNodeId());

        JsrEntryCIterRange jsr_range = entryMap.equal_range(stVar);
        JsrEntryInstToRetInstMap::const_iterator i;
        for(i = jsr_range.first; i != jsr_range.second; ++i) {
            assert((*i).first->getNode() == entryJSR);
            findNodesInRegion(entryJSR, (*i).second->getNode(), nodesInJSR);
        }

        // prepare the hash tables for rename translation
        OpndRenameTable    *opndRenameTable = new (inlineManager) OpndRenameTable(inlineManager,10);
        NodeRenameTable *nodeRenameTable = new (inlineManager) NodeRenameTable(inlineManager,10);

        Node* newEntry = FlowGraph::duplicateRegion(*irManager, entryJSR, nodesInJSR, defUses, *nodeRenameTable, *opndRenameTable, 0);

        fg.removeEdge(block,retTarget);
        fg.removeEdge(block,entryJSR);
        jsrInst->unlink();
        fg.addEdge(block, newEntry);

        //
        // Add edge from inline ret locations to return target.
        //
        for(i = jsr_range.first; i != jsr_range.second; ++i) {
            Node* inlinedRetNode = nodeRenameTable->getMapping((*i).second->getNode());
            Inst* ret = (Inst*)inlinedRetNode->getLastInst();
            assert(ret->isRet());
            assert(ret->getSrc(0) == retVar);
            ret->unlink();
            fg.addEdge(inlinedRetNode, retTarget);
        }

        //
        // delete the first two instructions of the inlined node
        // 
        assert(entryJSR != newEntry);
        saveReturn = findSaveRet(newEntry);
        assert(saveReturn);
        stVar = saveReturn->getNextInst();
        assert(stVar->isStVar() && (stVar->getSrc(0) == saveReturn->getDst()));
        retVar = stVar->getDst();

    }
    if(retVar != NULL) {
        ((VarOpnd *)retVar)->setDeadFlag(true); 
        stVar->unlink();
    }
    saveReturn->unlink();
    return TRUE;
}


static void inlineJSRs(IRManager* irManager) {
    MemoryManager jsrMemoryManager("FlowGraph::inlineJSRs.jsrMemoryManager");
    static CountTime inlineJSRTimer("ptra::fg::inlineJSRs");
    AutoTimer tm(inlineJSRTimer);

    JsrEntryInstToRetInstMap* jsr_entry_map = irManager->getJsrEntryMap();
    assert(jsr_entry_map); // must be set by translator

    if(Log::isEnabled()) {
        Log::out() << "JSR entry map:";
        JsrEntryInstToRetInstMap::const_iterator jsr_entry_it, jsr_entry_end;
        for ( jsr_entry_it = jsr_entry_map->begin(), 
            jsr_entry_end = jsr_entry_map->end(); 
            jsr_entry_it != jsr_entry_end; ++jsr_entry_it) {
                Log::out() << "--> [entry->ret]: ";
                jsr_entry_it->first->print(Log::out());
                Log::out() << " || ";
                jsr_entry_it->second->print(Log::out());
                Log::out() << std::endl;
            }
    }

    DefUseBuilder defUses(jsrMemoryManager);
    {
        static CountTime findJSRTimer("ptra::fg::inlineJSRs::defuse");
        AutoTimer tm(findJSRTimer);
        defUses.initialize(irManager->getFlowGraph());
    }

    ControlFlowGraph& fg = irManager->getFlowGraph();
    const Nodes& nodes = fg.getNodes();
    //Nodes nodes(jsrMemoryManager);
    //fg.getNodesPostOrder(nodes);
    //std::reverse(nodes.begin(), nodes.end());
    //WARN: new nodes created during the iteration 
    //we use the fact that new nodes added to the end of the collection here.
    for (U_32 idx = 0; idx < nodes.size(); ++idx) {
        Node* node = nodes[idx];
        Inst* last = (Inst*)node->getLastInst();
        if(last->isJSR()) {
            inlineJSR(irManager, node, defUses, *jsr_entry_map);
        }
    }
#ifdef _DEBUG
    const Nodes& nnodes = fg.getNodes();
    for (U_32 idx = 0; idx < nnodes.size(); ++idx) {
        Node* node = nnodes[idx];
        Inst* last = (Inst*)node->getLastInst();
        assert(!last->isJSR());
    }
#endif
}

// Finally inlining
static void _fixFinally(ControlFlowGraph& fg, Node *node, Node *retTarget) {
    // if the node has been visited, return
    if (node->getTraversalNum() >= fg.getTraversalNum()) {
        return;
    }
    node->setTraversalNum(fg.getTraversalNum());
    const Edges& outEdges = node->getOutEdges();
    Edges::const_iterator eiter;
    for(eiter = outEdges.begin(); eiter != outEdges.end(); ++eiter) {
        Edge* edge = *eiter;
        _fixFinally(fg, edge->getTargetNode(),retTarget);
    }

}


static void _fixBranchTargets(Inst *newInst, NodeRenameTable *nodeRenameTable) {
    // fix targets of instructions
    switch(newInst->getOpcode()) {
    case Op_Branch:
    case Op_JSR:
    case Op_Jump:
        {
            BranchInst *newBranch = (BranchInst*)newInst;
            Node *tar = newBranch->getTargetLabel()->getNode();
            if(nodeRenameTable->getMapping(tar) != NULL) {
                LabelInst *label = (LabelInst*)nodeRenameTable->getMapping(tar)->getFirstInst();
                newBranch->replaceTargetLabel(label);
            }
        }
        break;
    case Op_Switch:
        assert(0);
    default:
        break;
    }
}

// Finally inlining
bool FlowGraph::_inlineFinally(IRManager& irm, Node *from, Node *to, Node *retTarget,
                            NodeRenameTable *nodeRenameTable,
                            OpndRenameTable *opndRenameTable) {
    // if the node has been visited, return
    if (nodeRenameTable->getMapping(from) != NULL) return true;

    ControlFlowGraph& fg = irm.getFlowGraph();
    // if the node is epilogue, add and edge to it
    if (to->isExitNode()) {
       fg.addEdge(from,to);
       return true;
    }
    Node *newto = nodeRenameTable->getMapping(to);
    if (newto != NULL) {
        fg.addEdge(from,newto);
        return true;
    }
    // start following the control flow graph, duplicating basic blocks as needed
    newto = duplicateNode(irm, to, to, opndRenameTable);
    fg.addEdge(from,newto);
    nodeRenameTable->setMapping(to,newto);

    const Edges& outEdges = to->getOutEdges();
    Edges::const_iterator eiter;
    for(eiter = outEdges.begin(); eiter != outEdges.end(); ++eiter) {
        Edge* edge = *eiter;
        _inlineFinally(irm, newto,edge->getTargetNode(),retTarget,nodeRenameTable,opndRenameTable);
    }
    _fixBranchTargets((Inst*)newto->getLastInst(),nodeRenameTable);
    return true;
}


bool FlowGraph::inlineFinally(IRManager& irm, Node *block) {
    ControlFlowGraph& fg = irm.getFlowGraph();
    BranchInst* leaveInst  = (BranchInst*)block->getLastInst();
    Node *   retTarget  = leaveInst->getTargetLabel()->getNode();
    // record input operand
    Node *   entryFinally = NULL;
    const Edges& outEdges = block->getOutEdges();
    Edges::const_iterator eiter;
    for(eiter = outEdges.begin(); eiter != outEdges.end(); ++eiter) {
        Edge* edge = *eiter;
        Node *node = edge->getTargetNode();
        if (node != retTarget && !node->isDispatchNode()) {
            entryFinally = node;
            break;
        }
    }
    if (Log::isEnabled()) {
        Log::out() << "INLINE FINALLY\n";
        FlowGraph::printLabel(Log::out(), entryFinally);
        FlowGraph::printLabel(Log::out(), retTarget);
        Log::out() << std::endl;
        Log::out().flush();
    }
    if (entryFinally->hasOnlyOnePredEdge()) {
        fg.setTraversalNum(fg.getTraversalNum()+1);
        fg.removeEdge(block,retTarget);
        _fixFinally(fg, entryFinally,retTarget);
    } else {
        MemoryManager inlineManager("FlowGraph::inlineFinally.inlineManager");
        // prepare the hashtable for the operand rename translation
        OpndRenameTable    *opndRenameTable =
            new (inlineManager) OpndRenameTable(inlineManager,10);
        NodeRenameTable *nodeRenameTable =new (inlineManager) NodeRenameTable(inlineManager,10);
        fg.removeEdge(block,retTarget);
        fg.removeEdge(block,entryFinally);
        _inlineFinally(irm, block,entryFinally,retTarget, nodeRenameTable,opndRenameTable );
    }
    leaveInst->unlink();
    return true;
}


static void checkBCMapping(IRManager& irm) {
#ifdef _DEBUG
    ControlFlowGraph& fg = irm.getFlowGraph();
    const Nodes& nodes=  fg.getNodes();
    for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) {
    	Node* node = *it;
        if (!node->isEmpty()) { //allow empty nodes (like dispatches, exit, return nodes) do not have bc-mapping
            for (Inst* inst = (Inst*)node->getFirstInst(); inst!=NULL; inst = inst->getNextInst()) {
                if (inst->getOperation().canThrow() || inst->isLabel()) {
                    assert(inst->getBCOffset()!=ILLEGAL_BC_MAPPING_VALUE);
                }
            }
        }
    }
#endif
}

void FlowGraph::doTranslatorCleanupPhase(IRManager& irm) {
    U_32 id = irm.getCompilationContext()->getCurrentSessionNum();
    const char* stage = "trans_cleanup";
    if (Log::isLogEnabled(LogStream::IRDUMP)) {
        LogStream& irdump = Log::log(LogStream::IRDUMP);
        Log::printStageBegin(irdump.out(), id, "TRANS", stage, stage);
        irdump << OptPass::indent(irm) << "Trans:   Running " << "cleanup" << ::std::endl;
        Log::printIRDumpBegin(irdump.out(), id, stage, "before");
        printHIR(irdump.out(), irm.getFlowGraph(), irm.getMethodDesc());
        Log::printIRDumpEnd(irdump.out(), id, stage, "before");
    }

    ControlFlowGraph& fg = irm.getFlowGraph();
    InstFactory& instFactory = irm.getInstFactory();
    OpndManager& opndManager = irm.getOpndManager();


    static CountTime cleanupPhaseTimer("ptra::fg::cleanupPhase");
    AutoTimer tm(cleanupPhaseTimer);
    fg.purgeUnreachableNodes();

#ifdef _DEBUG
    //check if loop structure is valid after translator
    OptPass::computeLoops(irm, false);
#endif


    inlineJSRs(&irm);
    fg.purgeUnreachableNodes();

    checkBCMapping(irm);

    {
        static CountTime cleanupPhaseInternalTimer("ptra::fg::cleanupPhase::in");
        AutoTimer tm(cleanupPhaseInternalTimer);
        // Cleanup optimizations
        for (Nodes::const_iterator niter = fg.getNodes().begin(), end = fg.getNodes().end(); niter!=end; ++niter) {
            Node* node = *niter;
            if (node->isDispatchNode() || node == fg.getReturnNode() || node == fg.getExitNode()) {
                continue;
            }
            Inst *last = (Inst*)node->getLastInst();
            if (last->isBranch()) {
                if (last->isConditionalBranch()) { // loop peeling for conditional branches
                    Node *target  = ((BranchInst*)last)->getTargetLabel()->getNode();
                    if (((LabelInst*)target->getFirstInst())->getLabelId() > ((LabelInst*)node->getFirstInst())->getLabelId()) 
                    {
                        LabelInst *targetLabel = ((BranchInst*)last)->getTargetLabel();
                        Node *fthru = NULL, *taken = NULL;
                        const Edges& outEdges = node->getOutEdges();
                        Edges::const_iterator eIter;
                        for(eIter = outEdges.begin(); eIter != outEdges.end(); ++eIter) {
                            Edge* edge = *eIter;
                            Node * tar = edge->getTargetNode();
                            if (!tar->isDispatchNode()) {
                                if (tar->getFirstInst() == targetLabel) {
                                    taken = tar;
                                } else {
                                    fthru = tar; 
                                }
                            }
                        }
                        Inst *takenLdConst = (Inst*)taken->getSecondInst();
                        Inst *fthruLdConst = (Inst*)fthru->getSecondInst();
                        Inst *takenStVar   = (takenLdConst!=NULL) ? takenLdConst->getNextInst() : NULL;
                        Inst *fthruStVar   = (fthruLdConst!=NULL) ? fthruLdConst->getNextInst() : NULL;
                        if (takenStVar!=NULL && fthruStVar!=NULL                    &&
                            taken->hasOnlyOneSuccEdge()                             &&
                            taken->hasOnlyOnePredEdge()                             &&
                            fthru->hasOnlyOneSuccEdge()                             &&
                            fthru->hasOnlyOnePredEdge()                             &&
                            (taken->getOutEdges().front()->getTargetNode() ==
                            fthru->getOutEdges().front()->getTargetNode())         &&
                            takenLdConst->getOpcode()       == Op_LdConstant        &&
                            fthruLdConst->getOpcode()       == Op_LdConstant        &&
                            takenLdConst->getType()         == Type::Int32          &&
                            fthruLdConst->getType()         == Type::Int32          &&
                            takenStVar->getOpcode()         == Op_StVar             &&
                            fthruStVar->getOpcode()         == Op_StVar             &&
                            takenStVar->getDst()            == fthruStVar->getDst() &&
                            takenStVar->getNextInst()       == taken->getLastInst() &&
                            fthruStVar->getNextInst()       == fthru->getLastInst())
                        {

                                int takenint32 = ((ConstInst*)takenLdConst)->getValue().i4;
                                int fthruint32 = ((ConstInst*)fthruLdConst)->getValue().i4;
                                Node *meet = taken->getOutEdges().front()->getTargetNode();
                                // find the ldVar for the variable, if any
                                Inst *meetLdVar = (Inst*)meet->getSecondInst();
                                while (meetLdVar->getOpcode()==Op_LdVar) {
                                    if (meetLdVar->getSrc(0) == takenStVar->getDst())
                                        break;
                                    meetLdVar = meetLdVar->getNextInst();
                                }
                                if ((((takenint32==0) && (fthruint32==1)) ||
                                    ((takenint32==1) && (fthruint32==0))) &&
                                    meetLdVar->getOpcode()==Op_LdVar &&
                                    last->getNumSrcOperands()==2) {
                                        // change the instruction to reflect the compare instruction
                                        fg.removeEdge(node,taken);
                                        fg.removeEdge(node,fthru);
                                        fg.addEdge(node,meet);
                                        Opnd* dst = opndManager.createSsaTmpOpnd(meetLdVar->getDst()->getType());
                                        BranchInst *lastBranch = (BranchInst*)last;
                                        if (takenint32==0) 
                                            lastBranch->swapTargets(NULL);
                                        Inst *cmp = instFactory.makeCmp(
                                            lastBranch->getComparisonModifier(),
                                            lastBranch->getType(), dst, 
                                            lastBranch->getSrc(0),
                                            lastBranch->getSrc(1));
                                        cmp->insertBefore(lastBranch);
                                        Inst* newStVar = instFactory.makeStVar(meetLdVar->getSrc(0)->asVarOpnd(),dst);
                                        newStVar->insertBefore(lastBranch);
                                        lastBranch->unlink();
                                    }
                            }
                    }
                }
            }
            // remove trivial basic blocks
            if (node->hasOnlyOnePredEdge()) {
                Node *pred = node->getInEdges().front()->getSourceNode();
                if (!pred->isDispatchNode() &&  !((Inst*)pred->getLastInst())->isSwitch() &&
                    (pred->hasOnlyOneSuccEdge() ||  (node->isEmpty() && node->hasOnlyOneSuccEdge()))) 
                {                

                    // don't merge if the node has an exception edge 
                    Edge *edge = NULL;
                    Edges::const_iterator eiter;
                    for(eiter = node->getOutEdges().begin(); eiter != node->getOutEdges().end(); ++eiter) {
                        edge = *eiter;
                        if ((edge->getTargetNode())->isDispatchNode()) {
                            break;
                        }
                    }
                    // If the node has an exception edge, then merging is potentially illegal, so
                    // skip.
                    if (edge == NULL) {
                        if (Log::isEnabled()) {
                            Log::out()<<" MERGE ";FlowGraph::printLabel(Log::out(), pred);FlowGraph::printLabel(Log::out(), node);Log::out()<<"\n";
                            Log::out().flush();
                        }
                        BranchInst *branch = NULL;
                        if (!pred->hasOnlyOneSuccEdge() && node->isEmpty()) {
                            Inst* lastPred = (Inst*)pred->getLastInst();
                            Node* nodeSucc = node->getOutEdges().front()->getTargetNode();
                            if (lastPred->isBranch()) {
                                branch = (BranchInst*)lastPred;
                                if (branch->getTargetLabel() == node->getFirstInst()) {
                                    branch->replaceTargetLabel((LabelInst*)nodeSucc->getFirstInst());
                                }
                            }
                        }
                        fg.mergeBlocks(pred,node);

                        // remove useless branches
                        if (branch != NULL) {
                            Node *target = NULL;
                            for(eiter=pred->getOutEdges().begin(); eiter!=pred->getOutEdges().end();) {
                                Edge* edge = *eiter;
                                ++eiter;
                                Node *succ = edge->getTargetNode();
                                if (! succ->isDispatchNode()) {
                                    if (target == succ) {
                                        fg.removeEdge(pred,succ);
                                        branch->unlink();
                                        break;
                                    }
                                    target = succ;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    
    // Remove extra PseudoThrow insts
    DeadCodeEliminator dce(irm);
    dce.removeExtraPseudoThrow();

    //process all methods marked with @Inline pragma
    if (Log::isLogEnabled(LogStream::IRDUMP)) {
        LogStream& irdump = Log::log(LogStream::IRDUMP);
        Log::printIRDumpBegin(irdump.out(), id, stage, "before_pragma_inline");
        printHIR(irdump.out(), irm.getFlowGraph(), irm.getMethodDesc());
        Log::printIRDumpEnd(irdump.out(), id, stage, "before_pragma_inline");
    }
    Inliner::processInlinePragmas(irm);


    //
    // a quick cleanup of unreachable and empty basic blocks
    //
    fg.purgeUnreachableNodes();
    fg.purgeEmptyNodes(false);

    if (Log::isLogEnabled(LogStream::IRDUMP)) {
        LogStream& irdump = Log::log(LogStream::IRDUMP);
        Log::printStageEnd(irdump.out(), id, "TRANS", stage, stage);
    }

}

void FlowGraph::printHIR(std::ostream& os, ControlFlowGraph& fg, MethodDesc& methodDesc) {
    const char* methodName = methodDesc.getName();
    os << std::endl << "--------  irDump: " << methodDesc.getParentType()->getName() << "::" << methodName << "  --------" << std::endl;

    MemoryManager mm("ControlFlowGraph::print.mm");
    Nodes nodes(mm);
    fg.getNodesPostOrder(nodes);
    Nodes::reverse_iterator iter = nodes.rbegin(), end = nodes.rend();
    for(; iter != end; iter++) {
        Node* node = *iter;
        print(os, node);
        os << std::endl;
    }
}

void FlowGraph::print(std::ostream& os, Node* node) {
    os << "Block ";
    printLabel(os, node);
    os << ":  ";
    os << std::endl;

    // Print predecessors
    os << "  Predecessors:";
    const Edges& inEdges = node->getInEdges();
    for (Edges::const_iterator ite = inEdges.begin(), ende = inEdges.end(); ite!=ende; ++ite) {
        Edge* edge = *ite;
        os << " ";
        printLabel(os, edge->getSourceNode());
    }
    os << std::endl;

    // Print successors
    os << "  Successors:";
    const Edges& outEdges = node->getOutEdges();
    for (Edges::const_iterator ite = outEdges.begin(), ende = outEdges.end(); ite!=ende; ++ite) {
        Edge* edge = *ite;
        os << " ";
        printLabel(os, edge->getTargetNode());
    }
    os << std::endl;

    // Print instructions
    printInsts(os, node, 2);

}

void FlowGraph::printLabel(std::ostream& cout, Node* node) {
    Inst *first = (Inst*)node->getFirstInst();
    assert(first->isLabel());
    if (node->isBlockNode()) {
        if(node->getInDegree() == 0) {
            cout << "ENTRY_";
            ((LabelInst*)first)->printId(cout);
        } else if(node->getOutDegree() == 1 && node->getOutEdges().front()->getTargetNode()->isExitNode()) {
            cout << "RETURN";
        } else {
            ((LabelInst*)first)->printId(cout);
        }
    } else if (node->isDispatchNode()) {
        if(node->getOutDegree() == 1 && node->getOutEdges().front()->getTargetNode()->isExitNode())
            cout << "UNWIND";
        else
            cout << "D" << (I_32)((LabelInst*)first)->getLabelId();
    } else {
        cout << "EXIT";
    }
}

void FlowGraph::printInsts(std::ostream& cout, Node* node, U_32 indent){
    std::string indentstr(indent, ' ');
    Inst* inst = (Inst*)node->getFirstInst();
    while (inst!=NULL) {
        cout << indentstr.c_str();
        inst->print(cout); 
        cout << std::endl;
        inst = inst->getNextInst();
    }

    // The IR does not contain explicit GOTOs, so for IR printing purposes
    // we should print a GOTO if required, extracted from the CFG.
    inst = (Inst*)node->getLastInst();
    if (!inst->isReturn() && !inst->isThrow()  && !inst->isRet()) {
            Node *target = NULL;
            if (inst->isConditionalBranch()) {
                target = ((BranchInst*)inst)->getTakenEdge(false)->getTargetNode();
            } else {
                Edges::const_iterator j = node->getOutEdges().begin(), jend = node->getOutEdges().end();
                for (; j != jend; ++j) {
                    Edge* edge = *j;
                    Node *node = edge->getTargetNode();
                    if (!node->isDispatchNode()) {
                        target = node;
                        break;
                    }
                }
            }
            if (target != NULL) {
                cout << indentstr.c_str() << "GOTO ";
                printLabel(cout, target);
                cout << std::endl;
            }
        }
}

class HIRDotPrinter : public PrintDotFile {
public:
    HIRDotPrinter(ControlFlowGraph& _fg) : fg(_fg), loopTree(NULL), dom(NULL){}
    void printDotBody();
    void printDotNode(Node* node);
    void printDotEdge(Edge* edge);
private:
    ControlFlowGraph& fg;
    LoopTree* loopTree;
    DominatorTree* dom;
};

void FlowGraph::printDotFile(ControlFlowGraph& fg, MethodDesc& methodDesc,const char *suffix) {
    HIRDotPrinter printer(fg);
    printer.printDotFile(methodDesc, suffix);
}

void HIRDotPrinter::printDotBody() {
    const Nodes& nodes = fg.getNodes();
    dom = fg.getDominatorTree();
    if (dom != NULL && !dom->isValid()) {
        dom = NULL;
    }
    loopTree = fg.getLoopTree();
    if (loopTree!=NULL && !loopTree->isValid()) {
        loopTree = NULL;
    }
    for(Nodes::const_iterator niter = nodes.begin(); niter != nodes.end(); ++niter) {
        Node* node = *niter;
        printDotNode(node);
    }
    for(Nodes::const_iterator niter = nodes.begin(); niter != nodes.end(); ++niter) {
        Node* node = *niter;
        const Edges& edges = node->getOutEdges();
        for(Edges::const_iterator eiter = edges.begin(); eiter != edges.end(); ++eiter) {
            Edge* edge = *eiter;
            printDotEdge(edge);
        }
    }
}

void HIRDotPrinter::printDotNode(Node* node) {
    std::ostream& out = *os;
    FlowGraph::printLabel(out, node);
    out << " [label=\"";
    if (!node->isEmpty()) {
        out << "{";
    }
    ((Inst*)node->getFirstInst())->print(out);
    out << "tn: " << (int) node->getTraversalNum() << " pre:" << (int)node->getPreNum() << " post:" << (int)node->getPostNum() << " ";
    out << "id: " << (int) node->getId() << " ";
    if(fg.hasEdgeProfile()) {
        out << " execCount:" << node->getExecCount() << " ";
    }
    Node* idom = dom==NULL ? NULL: dom->getIdom(node);
    if (idom!=NULL) {
        out << "idom("; FlowGraph::printLabel(out, idom); out << ") ";
    }
    if (loopTree!=NULL) {
        Node* loopHeader = loopTree->getLoopHeader(node);
        bool isLoopHeader = loopTree->isLoopHeader(node);
        out << "loop(";
        if (!isLoopHeader) {
            out<<"!";
        }
        out<<"hdr";
        if (loopHeader!=NULL) {
            out<<" head:";FlowGraph::printLabel(out, loopHeader); 
        }
        out << ") ";
    }

    if (!node->isEmpty()) {
        out << "\\l|\\" << std::endl;
        Inst* first = (Inst*)node->getFirstInst();
        for (Inst* i = first->getNextInst(); i != NULL; i=i->getNextInst()) { // skip label inst
            i->print(out); 
            out << "\\l\\" << std::endl;
        }
        out << "}";
    }
    out << "\"";
    if (!node->isExitNode() && fg.hasEdgeProfile()) {
        double freq = node->getExecCount();
        double methodFreq = fg.getEntryNode()->getExecCount();
        if(freq > methodFreq*10) {
            out << ",color=red";
        } else if(freq > 0 && freq >= 0.85*methodFreq) {
            out << ",color=orange";
        }
    }
    if (node->isDispatchNode()) {
        out << ",shape=diamond,color=blue";
    } else if (node->isExitNode()) {
        out << ",shape=ellipse,color=green";
    } 
    
    out << "]" << std::endl;
}

void HIRDotPrinter::printDotEdge(Edge* edge) {
    std::ostream& out = *os;
    Node *from = edge->getSourceNode();
    Node *to   = edge->getTargetNode();
    FlowGraph::printLabel(out, from);
    out << " -> ";
    FlowGraph::printLabel(out, to);
    out<<" [";
    out << "taillabel=\"" ;
        if (loopTree) {
        if (loopTree->isBackEdge(edge)) {
            out<<"(backedge)";
        } 
        if (loopTree->isLoopExit(edge)) {
            out<<"(loopexit)";
        }
    }
    if (fg.hasEdgeProfile()) {
        out<<"p:" << edge->getEdgeProb();
    }
    out <<"\"";
    if (to->isDispatchNode()) {
        out << ",style=dotted,color=blue";
    }
    out << "];" << std::endl;
}

} //namespace Jitrino