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

/**
* @file
* The baseline implementation of control flow graph (CFG) and 
* CFG level routines.
* 
* The implementation can be reused and extended by different
* components as a base level for IR representation.
*/


#ifndef _CONTROLFLOWGRAPH_
#define _CONTROLFLOWGRAPH_ 


#include <assert.h>
#include <iostream>

#include "Dlink.h"
#include "Stl.h"

#include "open/types.h"

namespace Jitrino {

class Edge;
class Node;
class CFGInst;
class ControlFlowGraph;
class Type;
class DominatorTree;
class LoopTree;

typedef StlVector<Edge*> Edges;
typedef StlVector<Node*> Nodes;

  /**
   * The edge connecting two nodes in CFG and having a direction and type.
   * To extend the given class with a custom properties,
   * override the <code>createEdge</code> method 
   * of the ControlFlowGraphFactory class.
   */
class Edge {
  /** 
   * The ControlFlowGraph class that requires additional privileges to 
   * initialize protected fields of the Edge instance.
   */
    friend class ControlFlowGraph;
    
  /** 
   * The ControlFlowGraphFactory class that requires additional access privileges 
   * to access the protected constructor.
   */
    friend class ControlFlowGraphFactory;
public:
  /** 
   * The edge kind.
   * The edge kind depends on the <code>Source</code> and the
   * <code>Target</code> node kinds and is calculated
   * every time the <code>getKind</code> method is invoked.
   */
    enum Kind {        
        /// All edges to the <code>Dispatch</code> node (DN) are <code>Dispatch</code> edges.
        Kind_Dispatch = 1,       
        /// Jump, fall-through with no branch, indirect jump or edge to the <code>Exit</code> node.
        Kind_Unconditional = 2,  
        /// Fall-through after a not-taken branch, default target of switches (max one out-edge per node).
        Kind_False = 4,          
        /// A taken branch.
        Kind_True = 8,           
        /// All edges from DN to <code>Block</code> node (BNCFGInst::next() == CFGInst::prev() ) are <code>Catch</code> edges.
        Kind_Catch = 16          
    };
    
    /// The destructor. Does nothing.
    virtual ~Edge() {}


  /** 
   * ID is constant for the lifetime of the edge.
   *
   * @return The unique edge ID that is constant for lifetime of this edge.
   */
    U_32 getId() const {return id;}

  /** 
   * Returns the edge kind.
   *
   * @return The kind of the given edge.
   */

    virtual Kind getKind() const;

  /** 
   * Checks whether the edge is a <code>Dispatch</code> one, that is if the  
   * edge is of the Edge::Kind_Dispatch kind.
   *
   * @return <code>TRUE</code> for the Edge::Kind_Dispatch
   *         edge; otherwise, <code>FALSE</code>.
   */
    bool isDispatchEdge() const {return getKind() == Edge::Kind_Dispatch;}

  /** 
   * Checks whether the edge is an <code>Unconditional</code> one, that is if 
   * the edge is of the Edge::Kind_Unconditional kind.
   *
   * @return <code>TRUE</code> for the Edge::Kind_Unconditional
   *         edge; otherwise, <code>FALSE</code>.
   */
    bool isUnconditionalEdge() const {return getKind() == Edge::Kind_Unconditional;}

  /** 
   * Checks whether the edge is a <code>False</code> one, that is if the   
   * edge is of the Edge::Kind_False kind.
   *
   * @return <code>TRUE</code> for the Edge::Kind_False
   *         edge; otherwise, <code>FALSE</code>.
   */
    bool isFalseEdge() const {return getKind() == Edge::Kind_False;}

  /** 
   * Checks whether the edge is a <code>True</code> one, that is if the edge is  
   * of the Edge::Kind_True kind.
   *
   * @return <code>TRUE</code> for the Edge::Kind_True
   *         edge; otherwise, <code>FALSE</code>.
   */
    bool isTrueEdge() const {return getKind() == Edge::Kind_True;}

  /** 
   * Checks whether the edge is a <code>Catch</code> one, that is if the edge 
   * is of the Edge::Kind_Catch kind.
   *
   * @return <code>TRUE</code> for the Edge::Kind_Catch
   *         edge; otherwise, <code>FALSE</code>.
   */
    bool isCatchEdge() const {return getKind() == Edge::Kind_Catch;}

  /** 
   * Returns the <code>Source</code> node of the edge. The <code>Source</code>  
   * node is also called the <code><code>Tail</code></code> or <code>From</code> 
   * node.
   * 
   * @return The <code>Source</code> node of the edge.
   */
    Node* getSourceNode() const {return source;}

  /** 
   * Returns the <code>Target</code> node of the edge. The <code>Target</code>  
   * node is also called the <code>Head</code> or <code>To</code> node.
   * 
   * @return The <code>Target</code> node of the edge.
   */
    Node* getTargetNode() const {return target;}

  /** 
   * Returns the <code>Target</code> or the <code>Source</code> node depending  
   * on the <code>isForward</code> parameter.
   *
   * @param[in] isForward - tells which node to return
   *
   * @return If the <code>isForward</code> parameter is <code>True</code>, 
   *         returns the <code>Target</code> node; otherwise, 
   *         the <code>Source</code> node. 
   */
    Node* getNode(bool isForward) const {return isForward ? target : source;}


  /**
   * @return The probability of the edge.
   */
    double getEdgeProb() const {return prob;}
    
  /**
   * Sets the probability of the edge.
   *
   * @param[in] val - a new edge probability
   */
    void setEdgeProb(double val) {prob = val;}

protected:
   /** 
    * Initializes a new Edge instance.
    * The ID field is initialized with <code>MAX_UINT32</code>,
    * all other fields are initialized with 0.
    */
    Edge() : id (MAX_UINT32), source(NULL), target(NULL), prob(0) {}
    
   /** 
    * The helper method to set ID to the edge
    *
    * @param[in] _id - a new edge ID 
    */
    void setId(U_32 _id) {id = _id;}

    /// The unique edge ID within CFG.
    U_32 id;

    /// The <code>Source</code> or the <code>Tail</code> node of the edge.
    Node *source;
    
    /// The <code>Target</code> or the <code>Head</code> node of the edge.
    Node *target;

   /** The edge probability. 
     * If the ControlFlowGraph edge profile is valid, the sum of all 
     * outgoing edge probabilities for a node is equal to <code>1</code>.
     */
    double prob;
};


#define ILLEGAL_BC_MAPPING_VALUE 0xFFFF
  /** 
   * The base abstract class for all CFG instructions.
   * The given class keeps information about the node this instruction belongs
   * to, about previous and next instructions in the node and about instruction 
   * properties needed to perform CFG validity checks and to detect edge types  
   * for block-to-block edges correctly.
   * 
   * @note The CFGInst class behaves like <code>DLink</code>, 
   *       when none node is assigned to the instruction.
   */
class CFGInst : protected Dlink {
  /** 
   * The Node class needs additional privileges to 
   * initialize protected fields of the CFGInst instance.
   */
    friend class Node;

  /** 
   * The Edge class needs additional privileges to 
   * initialize protected fields of the CFGInst instance.
   */
    friend class Edge;

  /** 
   * The ControlFlowGraph class needs additional privileges to 
   * initialize protected fields of the CFGInst instance.
   */
    friend class ControlFlowGraph;
public:
    virtual ~CFGInst(){}

  /** 
   * Gets the current node the instruction belongs to. 
   *
   * @return The node instance the given instruction belongs to or   
   *         <code>NULL</code> if the instruction was unlinked or never added 
   *         to any node.
   */
    Node* getNode() const {return node;}
    
  /** 
   * Gets the next instruction.
   *
   * @return The next instruction in the node, or <code>NULL</code> if the 
   *         instruction is the last instruction in the node.
   *
   * @note The CFGInst class behaves like <code>DLink</code> when none 
   *       node is assigned to the instruction.
   */
    CFGInst* next() const; 
    
  /** 
   * Gets the previous instruction. 
   *
   * @return Returns the previous instruction in the node; if the instruction 
   *         is the first one in the node, returns <code>NULL</code>.
   *
   * @note The CFGInst class behaves like <code>DLinkM</code> when none node 
   *       is assigned to the instruction.
   */
    CFGInst* prev() const;

  /** 
   * Removes the instruction from the node.
   *
   * @note The CFGInst class behaves like <code>DLink</code> when none node 
   *       is assigned to the instruction.<br>
   *       CFGInst::next() == CFGInst::prev() == this after the call.
   */
    void unlink() {node = NULL; Dlink::unlink();}
    
  /** 
   * Inserts the instruction before <code>instBefore</code>. 
   * Assigns the node from <code>instBefore</code> to the instruction.
   *
   * @param[in] instBefore - the insertion point, before which the instruction 
   *                         goes 
   *                     
   * @note If the instruction is followed by other instructions, the call 
   *       inserts and assigns them to the node. Only instructions with the 
   *       <code>NULL</code> node can be inserted. 
   */
    void insertBefore(CFGInst* instBefore);
    
  /** 
   * Inserts the instruction after <code>instAfter</code>. 
   * Assigns the node from <code>instAfter</code> to the instruction.
   *
   * @param[in] instAfter - the insertion point, before which the instruction 
   *                        goes 
   *
   * @note If the instruction is followed by other instructions, the call 
   *       inserts and assigns them to the node.
   *       Only instructions with the <code>NULL</code> node can 
   *       be inserted.
   */
    void insertAfter(CFGInst* instAfter);

  /** 
   * Checks whether the instruction is the header critical one.
   * Only another header critical instruction can precede the 
   * header critical instruction.
   * CFG uses the given property to check validity when adding 
   * or removing instructions to the node.
   *
   * @return <code>TRUE</code> for the header critical instruction.
   */
    virtual bool isHeaderCriticalInst() const {return isLabel();}

  /** 
   * Checks whether the instruction is the label one.
   * Only one label instruction per node can exist.
   * CFG uses the given property to check validity when adding 
   * or removing instructions to the node.
   *
   * @return <code>TRUE</code> for the label instruction.
   *
   * @note The label instruction is also a header critical instruction.
   */
    virtual bool isLabel() const {return false;}

    /// Returns byte-code offset the inst
    uint16 getBCOffset() const { return bcOffset;}

    /// Sets byte-code offset the inst
    void setBCOffset(uint16 newVal) {bcOffset = newVal;}

protected:
    /// Called from CFG to detect edge kinds for BN to BN edges.
    virtual Edge::Kind getEdgeKind(const Edge* edge) const = 0;
    /// Called from CFG, when the edge target is replaced.
    virtual void updateControlTransferInst(Node* oldTarget, Node* newTarget) {}
    /// Called from CFG when two blocks are merging and one of the branches is redundant.
    virtual void removeRedundantBranch(){};

protected:
  /** 
   * The default constructor.
   * Initializes the Node instance field with the <code>NULL</code> 
   * value.
   */
    CFGInst() : node(NULL), bcOffset(ILLEGAL_BC_MAPPING_VALUE) {}

    /// The owner node of the instruction.
    Node* node;

    ///offset in byte-code
    uint16 bcOffset;
};

  /** 
   * The node representation and the base class for all nodes in CFG.
   * Three node classes in the control flow graph exist:
   * <code>Block</code> nodes, <code>Dispatch</code> nodes, and the 
   * <code>Exit</code> node.
   * All of them can contain an instruction.
   */
class Node {
  /** 
   * The ControlFlowGraph class that requires additional privileges to 
   * initialize protected fields of the <code>Node</code> instance.
   */
    friend class ControlFlowGraph;

  /** 
   * The ControlFlowGraphFactory class that requires additional privileges to 
   * access to the protected constructor of the <code>Node</code> instance.
   */
    friend class ControlFlowGraphFactory;

  /** 
   * The CFGInst class that requires additional privileges to 
   * initialize protected fields of the <code>Node</code> instance.
   */
    friend class CFGInst;
public:
  /** 
   * The kind of the node.
   * CFG has three node kinds:<br>
   * <ul><li>
   * <code>Kind_Block</code> - used for usual nodes with instructions<br>
   * <li><code>Kind_Dispatch</code> - used for exceptions paths. The 
   *                 <code>Dispatch</code> node connects the <code>Block</code> 
   *                 node throwing exception with another <code>Block</code> 
   *                 node catching the exception. 
   *                 If none <code>Block</code> node catches all possible   
   *                 exception types, the <code>Dispatch</code> node can also 
   *                 be connected with another <code>Dispatch</code> node.
   *                 To represent a path when an exception is not caught in
   *                 a current method, the <code>Unwind</code> node is used.<br> 
   * <li><code>Kind_Exit</code> - CFG has only one <code>Exit</code> node. The 
   *                 <code>Exit</code> node postdominates any exit path from
   *                 the methods. Only CFG without exits, like 
   *                 <code>While(True);</code> patterns, can have no
   *                 <code>Exit</code> node at all.</ul>
   */
    enum Kind {
        /// Basic <code>Block</code> node
        Kind_Block,      
        /// <code>Dispatch</code> node
        Kind_Dispatch,   
        /// <code>Exit</code> node
        Kind_Exit        
    };

    virtual ~Node() {}

  /**
   * Gets the kind of the node.
   *
   * @return The kind of the node.
   */
    Kind getKind() const {return kind;}

  /** 
   * Gets the unique node ID. The ID is unique for all nodes in the containing 
   * flow graph and is constant for the lifetime of this node. 
   * This method provides a sparse ID between zero
   * and the graph <code>getMaxNodeId()</code> value.
   *
   * @return The unique node ID in the containing flow graph.
   */
    U_32 getId() const {return id;}

  /** 
   * Gets the depth-first numbering of the given node computed during the last 
   * pass.
   * Use this number as a dense ID of the node until CFG is not modified.
   *
   * @return The depth of the first numbering of the given node.
   *
   * @note Df-numbering differes from pre-numbering by being recalculated only  
   *      after the direct graph ordering, that is when the  
   *      <code>isForward</code> parameter is <code>TRUE</code> in the 
   *      <code>orderNodes(isForward)</code> method call.
   */
    U_32 getDfNum() const {return dfNumber;}
    
  /** 
   * Gets the pre-num numbering of the given node computed during the last pass.
   * Use this number as a dense ID of the node until CFG is not modified.
   *
   * @return The pre-num numbering of the given node.
   */
    U_32 getPreNum() const {return preNumber;}
    
  /** 
   * Gets the post-num numbering of the given node computed during the last pass.
   * Use this number as a dense ID of the node until CFG is not modified.
   *
   * @return The post-num numbering of the given node.
   */
    U_32 getPostNum() const {return postNumber;}

    
  /**
   * Checks whether the node is a <code>Block</code> one.
   *
   * @return <code>TRUE</code> for the Node::Kind_Block node.
   */
    bool isBlockNode() const {return getKind() == Node::Kind_Block;}
    
  /** 
   * Checks whether the node is a <code>Dispatch</code> one.
   *
   * @return <code>TRUE</code> for the Node::Kind_Dispatch node.
   */
    bool isDispatchNode() const {return getKind() == Node::Kind_Dispatch;}
    
  /** 
   * Checks whether the node is an <code>Exit</code> one.
   *
   * @return <code>TRUE</code> for the Node::Kind_Exit node.
   */
    bool isExitNode() const {return getKind() == Node::Kind_Exit;}
    
  /** 
   * Checks whether the node is a <code>Catch</code> one.
   *
   * @return <code>TRUE</code> if the node is of the Node::Kind_Block kind and 
   *         the only incoming edge of the node is of the Edge::Kind_CatchEdge 
   *         kind.
   */
   bool isCatchBlock() const {return getInDegree() >=1 && getInEdges().front()->isCatchEdge();}

  /** 
   * Gets the incoming edges to the node.
   *
   * @return The collection of the incoming edges to the node.
   *
   * @note The ordering of edges in the collection is not specified.
   */
    const Edges& getInEdges() const {return inEdges;}
    
  /**
   * Gets the outgoing edges to the node.
   *
   * @return The collection of the outgoing edges to the node.
   *
   * @note The ordering of edges in the collection is not specified.
   */
    const Edges& getOutEdges() const {return outEdges;}

  /** 
   * Gets the incoming or outgoing edges to the node.
   *
   * @param[in] isForward - tells what kind of edges, incoming or outgoing, 
   *                        to return
   *
   * @return  If the <code>isForwarisForward</code> parameter is <code>TRUE</code>,
   *          returns the collection of incoming edges;
   *          otherwise, the collection of outgoing ones.
   *         
   * @note The ordering of edges in the collection is not specified.
   */
    const Edges& getEdges(bool isForward) const {return isForward ? outEdges : inEdges;}
    
  /** 
   * Gets the first outgoing edge that matches the <code>edgeKind</code> kind.  
   *
   * @param[in] edgeKind - the kind of the edge to find
   * 
   * @return The first outgoing edge matching the <code>edgeKind</code> parameter; 
   *         <code>NULL</code> if no edge of the specified kind has been found.
   *
   */
    Edge* getOutEdge(Edge::Kind edgeKind) const;

  /** 
   * Gets the first unconditional outgoing edge.  
   *
   * @return The first outgoing edge matching the Edge::Kind_Unconditional  
   *         parameter; <code>NULL</code> if no edge of the specified 
   *         kind has been found.
   *
   * @note The edge collections ordering is not specified.
   */
    Edge* getUnconditionalEdge() const {return getOutEdge(Edge::Kind_Unconditional);}

  /** 
   * Gets the outgoing edge with the Edge::Kind_False kind.  
   *
   * @return The first outgoing edge matching the Edge::Kind_False
   *         parameter; <code>NULL</code> if no edge of the specified 
   *         kind has been found.
   *
   * @note The only one outgoing edge of the Edge::Kind_False kind is 
   *       allowed per node.
   */
    Edge* getFalseEdge() const {return getOutEdge(Edge::Kind_False);}

  /** 
   * Gets the first <code>True</code> outgoing edge.
   *
   * @return The first outgoing edge matching the Edge::Kind_True 
   *        parameter; <code>NULL</code> if no edge of the specified 
   *        kind has been found.
   *
   * @note The edge collections ordering is not specified.
   */
    Edge* getTrueEdge() const {return getOutEdge(Edge::Kind_True);}
    
  /** 
   * Gets the outgoing edge of the Edge::Kind_Dispatch kind.
   *
   * @return The first outgoing edge matching the Edge::Kind_Dispatch
   *         parameter; <code>NULL</code> if no edge of the specified 
   *         kind has been found.
   *
   * @note The only one outgoing edge of the Edge::Kind_Dispatch kind is 
   *       allowed per node.
   */
    Edge* getExceptionEdge() const {return getOutEdge(Edge::Kind_Dispatch);}

  /** 
   * Checks whether the node is connected to <code>anotherNode</code>.
   *
   * @param[in] isForward   - the direction of the connection. If <code>TRUE</code> 
   *                          the outgoing edges are checked, if <code>FALSE</code> 
   *                          the incoming edges are checked.
   *
   * @param[in] anotherNode - the node to check connection with
   *
   * @return <code>TRUE</code> if the node is connected with <code>anotherNode</code>  
   *         using <code>isForward</code> edges; otherwise, returns <code>FALSE</code>, 
   *         or <code>TRUE</code>. 
   */
    bool  isConnectedTo(bool isForward, Node* anotherNode) const {return findEdgeTo(isForward, anotherNode)!=NULL;}


  /** 
   * Finds the edge connected to <code>anotherNode</code>.
   *
   * @param[in] isForward - the direction of the connection. If <code>TRUE</code> 
   *                        the outgoing edges are checked, if <code>FALSE</code> 
   *                        the incoming edges are checked.
   * 
   * @param[in] anotherNode - the node that the edge connects to
   *
   * @return The edge connects the node and the <code>anotherNode</code> with 
   *         the direction <code>isForwarisForward</code>; 
   *         otherwise <code>NULL</code>. 
   */
    Edge*  findEdgeTo(bool isForward, Node* anotherNode) const;
    
  /** 
   * Finds the first outgoing edge with the specified kind 
   * and returns its <code>Target</code> node.
   *
   * @param[in] edgeKind - the kind of the edge to find
   *
   * @return The <code>Target</code> node of the outgoing edge of the 
   *         <code>edgeKind</code> kind; <code>NULL</code> if such an
   *         edge has not beed found.
   *
   */
    Node* getEdgeTarget(Edge::Kind edgeKind) const {Edge* edge = getOutEdge(edgeKind); return edge == NULL ? NULL : edge->getTargetNode();}

  /** 
   * Finds the first unconditional outgoing edge and returns its 
   * <code>Target</code> node.
   *
   * @return The <code>Target</code> node of the outgoing edge of 
   *         the Edge::Kind_Unconditional kind; <code>NULL</code>
   *         if such an edge has not beed found.
   *
   */
    Node* getUnconditionalEdgeTarget() const {return getEdgeTarget(Edge::Kind_Unconditional);}

  /** 
   * Finds the <code>False</code> outgoing edge and returns its 
   * <code>Target</code> node.
   *
   * @return The <code>Target</code> node of the outgoing edge of 
   *         the Edge::Kind_False kind; <code>NULL</code> if such an 
   *         edge has not beed found.
   */
    Node* getFalseEdgeTarget() const  {return getEdgeTarget(Edge::Kind_False);}

  /** 
   * Finds the first <code>True</code> outgoing edge and returns its 
   * <code>Target</code> node.
   *
   * @return The <code>Target</code> node of the outgoing edge of the 
   *         Edge::Kind_True kind; <code>NULL</code> if such an edge 
   *         has not beed found.
   *
   */
    Node* getTrueEdgeTarget() const  {return getEdgeTarget(Edge::Kind_True);}

  /** 
   * Finds the <code>Dispatch</code> edge and returns its <code>Target</code> 
   * node.
   *
   * @return The <code>Target</code> node of the outgoing edge of the 
   *         Edge::Kind_Dispatch kind; <code>NULL</code> if such an edge
   *         has not beed found.
   */
    Node* getExceptionEdgeTarget() const  {return getEdgeTarget(Edge::Kind_Dispatch);}
    
  /** 
   * Finds the edge connecting the node with <code>anotherNode</code>.
   *
   * @param[in] isForward   - the search in the outgoing edges, if  
                              <code>TRUE</code>; otherwise, in the incoming edges 
   * @param[in] anotherNode - the node connected with the given node by the edge
   *
   * @return The edge connecting the node with <code>anotherNode</code>;
   *         otherwise, <code>NULL</code>.
   */
    Edge* findEdge(bool isForward, const Node* anotherNode) const;

  /** 
   * Finds the incoming edge connecting the node with <code>anotherNode</code>.
   *
   * @param[in] anotherNode - the node connected with the given node by the edge
   *
   * @return The incoming edge connecting the node with <code>anotherNode</code>;
   *         otherwise, <code>NULL</code>.
   */
    Edge* findSourceEdge(const Node* source) const {return findEdge(false, source);}

  /** 
   * Finds the outgoing edge connecting the node with <code>anotherNode</code>.
   *
   * @param[in] anotherNode - the node connected with the given node by the edge
   *
   * @return The outgoing edge connecting the node with <code>anotherNode</code>;
   *         otherwise, <code>NULL</code>.
   */
    Edge* findTargetEdge(const Node* target) const {return findEdge(true, target);}
    
  /** 
   * Gets the number of outgoing edges of the node. 
   *
   * @return The number of outgoing edges of the node.
   */
    U_32 getOutDegree() const {return (U_32)getOutEdges().size();}
    
  /** 
   * Gets the number of incoming edges to the node. 
   *
   * @return The number of incoming edges to the node.
   */
    U_32 getInDegree() const {return (U_32)getInEdges().size();}

  /** 
   * Checks whether the node has only one outgoing edge. 
   * 
   * @return <code>TRUE</code> if the node has only one outgoing edge;
   *         otherwise, <code>FALSE</code>.
   */
    bool hasOnlyOneSuccEdge() const {return getOutDegree() == 1;}
    
  /** 
   * Checks whether the node has only one incoming edge. 
   * 
   * @return <code>TRUE</code> if the node has only one incoming edge;
   *         otherwise, <code>FALSE</code>.
   */
    bool hasOnlyOnePredEdge() const {return getInDegree() == 1;}

  /** 
   * Checks whether the node has two or more outgoing edges.
   * 
   * @return <code>TRUE</code> if the node has two or more outgoing edges;
   *         otherwise, <code>FALSE</code>.
   */
    bool hasTwoOrMoreSuccEdges() const {return getOutDegree() >= 2;}

  /** 
   * Checks whether the node has two or more incoming edges.
   * 
   * @return <code>TRUE</code> if the node has two or more incoming edges;
   *         otherwise, <code>FALSE</code>.
   */
    bool hasTwoOrMorePredEdges() const {return getInDegree() >= 2;}


  /** 
   * Appends the instruction to the node instruction list after the 
   * <code>instBefore</code> instruction.
   * If the instruction is a list, then the whole list is added.
   *
   * @param[in] newInst    - a new instruction/instructions list to add
   * @param[in] instBefore - the location where to insert new instructions. 
   *                          If <code>instBefore</code> is <code>NULL</code>, 
   *                          new instructions are appended to the end of the 
   *                          node list; otherwise, they are inserted right  
   *                          after <code>instBefore</code>.
   */
    void appendInst(CFGInst* newInst, CFGInst* instBefore = NULL);

  /** 
   * Prepends the instruction to the node instruction list before the 
   * <code>instAfter</code> instruction.
   * If the instruction is a list, then the whole list is added.
   *
   * @param[in] newInst   - a new instruction/instructions list to add
   * @param[in] instAfter - the location where to insert new instructions. 
   *                        If <code>instAfter</code> is <code>NULL</code>, new 
   *                        instructions are prepended to the beginning of the 
   *                        node list; otherwise, they are inserted right  
   *                        before <code>instBefore</code>.
   */
    void prependInst(CFGInst* newInst, CFGInst* instAfter = NULL);
    
  /** 
   * Counts the number of instructions in the node. The complexity of 
   * the algorithm is proportional to the number of instructions.
   *
   * @return  The number of instructions in the node. 
   */
    U_32 getInstCount(bool ignoreLabels = true) const;

  /** 
   * Checks whether not a single instruction is in the node.
   *
   * @param[in] ignoreLabels - tells whether to count label instructions
   * 
   * @return  <code>TRUE</code> not a single instruction is in the node.
   */
    bool isEmpty(bool ignoreLabels = true) const {CFGInst* inst = getFirstInst(); return inst == NULL || (ignoreLabels && inst->isLabel() && inst->next() == NULL);}

  /** 
   * Gets the first instruction in the node.
   *
   * @return  The first instruction in the node;
   *          <code>NULL</code> if the node is empty.
   */
    CFGInst* getFirstInst() const {return instsHead->getNext() != instsHead ? (CFGInst*)instsHead->getNext() : NULL;}

  /** 
   * Gets the last instruction in the node.
   *
   * @return  The last instruction in the node;
   *          <code>NULL</code> if the node is empty.
   */
    CFGInst* getLastInst() const {return instsHead->getPrev() != instsHead ? (CFGInst*)instsHead->getPrev() : NULL;}

  /** 
   * Gets the execution count of the node. Execution count of the node is 
   * a number of times the code of this node was executed at run time. 
   * This number can be the result of profiling of static estimation.
   * 
   * @return  The number of times the code of the given node was executed.
   */
    double getExecCount() const {return execCount;}

  /** 
   * Sets the execution count for the node.
   *
   * @param[in] val - a new execution count value
   */
    void setExecCount(double val) {execCount = val;}


  /**
   * Gets the current node traversal number used by internal and external 
   * algorithms to mark node as visited.
   *
   * @return The traversal number for the node.
   */
    U_32 getTraversalNum() const {return traversalNumber;}
    
  /** 
   * Sets a new traversal number of the node, usually 
   * <code>oldTraversalNumber</code> + 1.
   *
   * @param[in] num - a new traversal number
   */
    void setTraversalNum(U_32 num) {traversalNumber = num;}

  /** 
   * Gets the second instruction in the node.
   *
   * @return  The second instruction in the node;
   *          <code>NULL</code> if the node is empty or has only one 
   *          instruction. 
   */
    CFGInst* getSecondInst() const {return isEmpty() ? NULL : getFirstInst()->next();}
    
  /** 
   * Gets the label instruction. The label instruction is always the first 
   * instruction in the node. Check additionally whether the first instruction 
   * is a label one.
   * 
   * @return  The first instruction or <code>NULL</code>. 
   *          Checks whether the first instruction is a label one.
   */
    CFGInst* getLabelInst() const {CFGInst* first = getFirstInst(); assert(first==NULL || first->isLabel()); return first;}


    /** 
    * Gets bytecode offset of the first inst with bc-mapping in the node
    * 
    * @return  bytecode offset of the first inst with bc-mapping in the node
    */
    uint16 getNodeStartBCOffset() const;

    /** 
    * Gets bytecode offset of the last inst with bc-mapping in the node
    * 
    * @return  bytecode offset of the last inst with bc-mapping in the node
    */
    uint16 getNodeEndBCOffset() const;


protected:
  /** 
   * The constructor of Node.
   * Initializes all instance fields with default values.
   * 
   * @param[in] mm   - the memory manager to use
   * @param[in] kind - the node kind
   */
    Node(MemoryManager& mm, Kind kind);
    
  /**
   * Sets the node ID.
   * 
   * @param[in] _id - a new node ID 
   */
    void setId(U_32 _id) {id = _id;}


  /**
   * Inserts the <code>newInst</code> instruction right after 
   * the <code>prev</code> instruction.
   * Assigns the node to the <code>newInst</code>.
   */
    void insertInst(CFGInst* prev, CFGInst* newInst);

    /// The unique ID of the node in CFG.
    U_32 id;
    
  /** 
   * The depth-first number of the node in CFG. 
   * It is updated every time CFG is ordered.
   */
    U_32 dfNumber;

  /** 
   * The pre-number of the node in CFG. 
   * It is updated every time CFG is ordered.
   */
    U_32 preNumber;
    
  /** 
   * The post-number of the node in CFG. 
   * It is updated every time CFG is ordered.
   */
    U_32 postNumber;

  /** 
   * The number of times the node was traversed by the 
   * ordering algorithms.
   * It is updated every time CFG is ordered.
   */
    U_32 traversalNumber;

    /// The type of the node.
    Kind   kind;

  /** 
   * The collection of all incoming edges to the node. 
   * The order of edges in this collection if not specified.
   */
    Edges inEdges;

  /** 
   * The collection of all outgoing edges from the node. 
   * The order of edges in this collection if not specified.
   */
    Edges outEdges;
    
   /** 
    * The stub for the node instructions list.
    * The first user's instruction in the node is the first instruction
    * after the <code>instHead</code> stub.
    * The last user's instruction in the node is the first instruction
    * before the <code>instHead</code> stub.
    */
    CFGInst* instsHead;

    /// Profiling information. The number of times this node was executed.
    double execCount;
};

  /** 
   * The factory class for nodes and edges.
   * Creates nodes and edges at ControlFlowGraph requests.
   * The default implementation of the given class creates default nodes
   * and edges of the <code>Node</code> and <code>Edge</code> classes. 
   * To create custom <code>Node</code> and <code>Edge</code> subclasses,overload
   * the methods of the given factory class.
   */
class ControlFlowGraphFactory {
public:
    ///The default constructor for the ControlFlowGraphFactory class. Does nothing.
    ControlFlowGraphFactory(){}
    ///The default destructor for the ControlFlowGraphFactory class. Does nothing.
    virtual ~ControlFlowGraphFactory(){}
    
  /** 
   * Creates a new Edge of the specified kind using the memory manager as the 
   * allocator.
   * 
   * @param[in] mm   - the memory manager for the newly created node
   * @param[in] kind - the kind of the newly created node
   * 
   * @return A new specified node allocated on the memory manager.
   */
    virtual Node* createNode(MemoryManager& mm, Node::Kind kind);

  /** 
   * Creates a new Edge of the specified kind to connect nodes of  
   * <code>srcKind</code> and <code>dstKind</code> kinds.
   *
   * @param[in] mm      - the memory manager for the newly created edge
   * @param[in] srcKind - the kind of <code>Source</code> node for the edge
   * @param[in] dstKind - the kind of source <code>Target</code> for the edge
   *  
   * @return A new edge allocated on the memory manager to be connected with
   *         nodes of <code>srcKind</code> and <code>dstKind</code> kinds.
   */
    virtual Edge* createEdge(MemoryManager& mm, Node::Kind srcKind, Node::Kind dstKind);
};


  /** 
   * The base class for CFG.
   * The container class for nodes, edges, global states of nodes and edges and 
   * related algorithms.
   */
class ControlFlowGraph {
public:

  /** 
   * Creates new CFG.
   *
   * @param[in] mm      - the memory manager for CFG nodes, edges and internal data
   * @param[in] factory - the factory to create new nodes and edges
   *
   * If no factory is specified, the default factory implementation is used.
   */
    ControlFlowGraph(MemoryManager& mm, ControlFlowGraphFactory* factory = NULL);
    virtual ~ControlFlowGraph(){};
    
  /** 
   * Gets a collection of all nodes in the graph.  
   * Certain nodes in the collection can be unreachable.
   * The order of nodes is arbitrary.
   *
   * @return A collection of nodes in the control flow graph.
   *
   * @note All iterators to the collection become invalid when new nodes 
   *       are added or old ones deleted.
   */
    const Nodes& getNodes() const {return nodes;}
    
  /**  
   * Gets the unique <code>Entry</code> node. The given node dominates all other nodes in 
   * the graph.
   * The <code>Entry</code> node has the <code>Node::Kind_BlockNode</code> kind.
   * 
   * @return  The <code>Entry</code> node.
   */
    Node* getEntryNode() const {return entryNode;}

  /** 
   * Sets the <code>Entry</code> node. The given node dominates all other nodes 
   * in the graph.
   * The <code>Entry</code> node must be a block one.
   * 
   * @param[in] e - a new <code>Entry</code> node
   */
    void setEntryNode(Node* e) {assert(e!=NULL); entryNode = e; lastModifiedTraversalNumber = traversalNumber;}
    
  /**  
   * Gets the unique <code>Exit</code> node. The given node postdominates all other nodes
   * in the graph except child nodes of infinite loops.
   * The <code>Exit</code> node has the Node::Kind_ExitNode kind.
   * 
   * @return  The <code>Exit</code> node.
   */
    Node* getExitNode() const {return exitNode;}

  /** 
   * Sets the <code>Exit</code> node. The given node postdominates all other
   * nodes in the graph except child nodes of infinite loops.
   * The <code>Exit</code> node has the Node::Kind_ExitNode kind.
   *
   * @return  The <code>Exit</code> node.
   */
    void setExitNode(Node* e) {assert(e!=NULL); exitNode = e; lastModifiedTraversalNumber = traversalNumber;}

  /** 
   * Gets the unique block node that postdominates all nodes
   * in all paths that are non-dispatch exits from the method.
   *
   * @return The <code>Return</code> node of the graph.
   */
    Node* getReturnNode() const {return returnNode; }
    
  /**  
   * Sets the <code>Return</code> node for the graph. 
   * The <code>Return</code> node is a block node that postdominates all
   * nodes in all paths that are non-dispatch exits from the method.
   *
   * @return The <code>Return</code> node of the graph.
   */
    void setReturnNode(Node* node) {assert(returnNode==NULL); assert(node->isBlockNode()); returnNode = node;}
        
  /**  
   * Gets the unique dispatch node that postdominates all nodes
   * in all paths that are dispatch exits from the method.
   *
   * @return The <code>Unwind</code> node of the graph.
   */
    Node* getUnwindNode() const {return unwindNode;}

  /**
   * Sets the <code>Unwind</code> node for the graph. 
   * The <code>Unwind</code> node is a dispatch node that postdominates all 
   * nodes in all paths that are dispatch exits from the method.
   *
   * @return The <code>Unwind</code> node of the graph.
   */
    void setUnwindNode(Node* node) {assert(node->isDispatchNode()); unwindNode = node;}

  /** 
   * Gets the maximum node ID. 
   * The given ID is incremented any time the node is added to the graph.
   * 
   * @return The maximum node ID.
   */
    U_32 getMaxNodeId() const {return nodeIDGenerator;}
    
  /** 
   * Creates a new specified node. Add instruction to the node.
   * 
   * @param[in] kind - the kind of the node
   * @param[in] inst - the instruction to add to the node instructions list
   * 
   * @return A newly created node.
   */
    Node* createNode(Node::Kind kind, CFGInst* inst = NULL);

  /** 
   * Creates a new <code>Block</code> node and adds the instruction 
   * to it.
   * 
   * @param[in] inst - the instruction to add to the node instructions list
   * 
   * @return A newly created node.
   */
    Node* createBlockNode(CFGInst* inst = NULL) {return createNode(Node::Kind_Block, inst);}
    
  /** 
   * Creates a new <code>Dispatch</code> node and adds the instruction 
   * to it.
   * 
   * @param[in] inst - the instruction to add to the node instructions list
   * 
   * @return A newly created node.
   */
    Node* createDispatchNode(CFGInst* inst = NULL) {return createNode(Node::Kind_Dispatch, inst);}

  /** 
   * Creates a new <code>Exit</code> node and adds the instruction 
   * to it.
   * 
   * @param[in] inst - the instruction to add to the node instructions list
   *
   * @return A newly created node.
   */
    Node* createExitNode(CFGInst* inst = NULL) {return createNode(Node::Kind_Exit, inst);}
        
  /** 
   * Removes the node and all its incoming and outgoing edges from the graph.
   * 
   * @param[in] node - a node to remove 
   */
    void removeNode(Node* node);

  /** 
   * Gets the number of nodes in the graph that are reachable from the <code>Entry</code> node.
   * Orders nodes and updates traversal and ordering numbers of the graph and all 
   * nodes if the graph has been modified from the last ordering.
   *
   * @return The number of reachable nodes in the graph.
   */
    U_32 getNodeCount() { if(!hasValidOrdering()) orderNodes(); return nodeCount; }
    
  /** 
   * Gets the cached postorder collection of nodes in the graph.
   * 
   * @return The collection of nodes ordered in postorder.
   */
    const Nodes& getNodesPostOrder() {if (!hasValidOrdering()) orderNodes(); return postOrderCache;}
    
  /** 
   * Copies pointers to all nodes of the graph to the container.
   * 
   * @param[in] container - a container to put node pointers to
   *
   * The container must provide the <code>Insert</code>(<code>iterator 
   * insertLocation</code>, <code>iterator start</code>, <code>iterator 
   * end</code>) method.
   */
    template <class Container>
        void getNodes(Container& container) {
            container.insert(container.begin(), nodes.begin(), nodes.end());
        }

  /** 
   * Copies post-ordered nodes sequence to the container.
   * If <code>isForwarisForward</code> is <code>TRUE</code>, the method starts 
   * ordering the DFS algorithm from the <code>Entry</code> node.  
   * If <code>isForwarisForward</code> is <code>FALSE</code>, the method starts 
   * ordering the DFS algorithm from the <code>Exit</code> node.
   *
   * @param[in] container - the container to add nodes
   * @param[in] isForward - whether to start DFS ordering from the <code>Entry</code> 
   *                       (<code>TRUE</code>) or <code>Exit</code> 
   *                       (<code>FALSE</code>) node
   * 
   * @note The container class must provide the <code>push_back(Node*)</code> 
   * method.
   */
    template <class Container>
    void getNodesPostOrder(Container& container, bool isForward=true) {
        runDFS((Container*) NULL, &container,  isForward);
    }


  /** 
   * Copies pre-ordered nodes sequence to the container.
   * If <code>isForwarisForward</code> is <code>TRUE</code>, the method starts 
   * ordering the DFS algorithm from the <code>Entry</code> node.
   * If <code>isForwarisForward</code> is <code>FALSE</code>, the method starts  
   * ordering the DFS algorithm from the <code>Exit</code> node.
   * 
   * @param[in] container - the container to add nodes
   * @param[in] isForward - whether to start DFS ordering from the <code>Entry</code> 
   *                       (<code>TRUE</code>) or <code>Exit</code> 
   *                       (<code>FALSE</code>) node
   *  @note The container class must provide the <code>push_back(Node*)</code> 
   *        method.
   */
    template <class Container>
    void getNodesPreOrder(Container& container, bool isForward=true) {
        runDFS(&container, (Container*) NULL, isForward);
    }

    
  /** 
   * Orders the nodes in the graph. 
   * If <code>isForward</code> is <code>TRUE</code>, updates the  
   * internal CFG collection of nodes and node df-numbers.
   * Affects nodes and graph traversal and ordering numbers.
   *  
   * @param[in] isForward - whether to start DFS ordering from the <code>Entry</code> 
   *                        (<code>TRUE</code>) or <code>Exit</code> 
   *                        (<code>FALSE</code>) node
   * 
   */
    void orderNodes(bool isForward=true) {
        runDFS((Nodes*) NULL, (Nodes*) NULL, isForward);
    }

  /** 
   * Creates a new edge from the <code>Source</code> node to the 
   * <code>Target</code> one. 
   * 
   * @param[in] source   - the <code>Source</code> or <code>Tail</code> 
   *                       node for the edge
   * @param[in] target   - the <code>Target</code> or <code>Head</code> 
   *                       node for the edge
   * @param[in] edgeProb - the probability of the edge
   * 
   * @return The newly created edge.
   */
    Edge* addEdge(Node* source, Node* target, double edgeProb = 1.0);


  /** 
   * Gets the maximum edge ID. 
   * The given ID is incremented every time the edge is added to the graph.
   * 
   * @return The maximum edge ID.
   */
    U_32 getMaxEdgeId() const {return edgeIDGenerator;}

  /** 
   * Removes the edge from CFG. Updates <code>Source</code> and 
   * <code>Target</code> nodes. 
   * Does not affect other edge probabilities.
   * 
   * @param[in] edge - the edge to remove
   */
    void  removeEdge(Edge* edge);

  /** 
   * Removes the edge connecting <code>Source</code> and 
   * <code>Target</code> nodes. 
   * Updates <code>Source</code> and <code>Target</code> nodes. Does not  
   * affect other edge probabilities.
   * 
   * @param[in] source - the <code>Source</code> node for the edge
   * @param[in] target - the <code>Target</code> node for the edge
   */
    void  removeEdge(Node* source, Node* target) {removeEdge(source->findTargetEdge(target));}
    
  /** 
   * Removes the edge, creates a new one and connects it to 
   * the <code>newTarget</code> node.
   *
   * @param[in] edge        - the edge to change the target
   * @param[in] newTarget   - a new <code>Target</code> node
   * @param[in] keepOldEdge - modify old or create a new edge
   * 
   * @return The edge connecting the <code>Source</code> node of the  
   *         edge and the </code>newTarget</code> node.
   *
   * @note The removal of the old edge is needed
   *       while inlining CFG: edge IDs must be renewed.
   */
    Edge* replaceEdgeTarget(Edge* edge, Node *newTarget, bool keepOldEdge = false);

  /** 
   * Checks if CFG is annotated with the edge profile information.
   * 
   * @return <code>TRUE</code> if CFG was annotated with the edge profile.
   */
    bool hasEdgeProfile() const {return annotatedWithEdgeProfile;}

  /** 
   * Sets if CFG is annotated with the edge profile.
   * 
   * @param[in] val - marks CFG as annotated if <code>val</code> is <code>TRUE</code>, 
   *                  CFG is not annotated if <code>val</code> is <code>FALSE</code>.
   */
    void setEdgeProfile(bool val) {annotatedWithEdgeProfile = val;}


  /** 
   * Checks if the edge profile is consistent. 
   * Checks only reachable nodes and recalculates postorder cache if needed.
   * 
   * @param[in] checkEdgeProbs  - enables edge probs consistency check. If for every 
   *                              node the sum of the all outgoing edge probs 
   *                              is equal to 1.0, the edge probs data is consistent.
   * 
   * @param[in] checkExecCounts - enables exec counts consistency check. If for every 
   *                              node the sum of exec counts of incoming edges is 
   *                              equal to the node exec count, the exec count data  
   *                              is consistent.
   * @param[in] doAssert        - asserts if the consistency error is found. Useful 
   *                              to position the debugger to the error.
   */
    bool isEdgeProfileConsistent(bool checkEdgeProbs = true, bool checkExecCounts = true, bool doAssert=false);
    
  /** 
   * Counts the execution counts of nodes using edge probabilities and execution 
   * count of the <code>Entry</code> node.
   */
    void smoothEdgeProfile();


  /** 
   * Gets the traversal number.
   * The traversal number is analogous to a monotonically increasing timestamp.
   * It is updated anytime an ordering traversal is performed on CFG.
   * If a modification was performed after an ordering, the ordering is invalid.
   *
   * @return The traversal number
   */
    U_32 getTraversalNum() const {return traversalNumber;}
    
  /** 
   * Sets the traversal number.
   * The traversal number is analogous to a monotonically increasing timestamp.
   * It is updated anytime an ordering traversal is performed on CFG.
   * If a modification was performed after an ordering, the ordering is invalid.
   *
   * @param[in] newTraversalNum - a new traversal number
   */

    void setTraversalNum(U_32 newTraversalNum) {traversalNumber = newTraversalNum;}

  /** 
   * The modification traversal number is the traversal number of the
   * last add/remove of a node/edge in the graph.
   * 
   * @return The modification traversal number.
   */
    U_32 getModificationTraversalNum() const { return lastModifiedTraversalNumber; }

  /** 
   * The edge removal traversal number is the modification traversal number of 
   * the last remove of an edge in the graph.
   * 
   * @return The edge removal traversal number.
   */
    U_32 getEdgeRemovalTraversalNum() const { return lastEdgeRemovalTraversalNumber; }

  /** 
   * The ordering traversal number is the traversal number after the last depth
   * first ordering. Node pre/post numbers are valid, if
   * getOrderingTraversalNum() is greater than getModificationTraversalNum().
   *
   * @return The ordering traversal number.
   */
    U_32 getOrderingTraversalNum() const { return lastOrderingTraversalNumber; }

  /** 
   * Checks if CFG nodes have valid ordering, that is there was no modification
   * in graph from the time of the last ordering.
   *
   * @return <code>TRUE</code> if ordering is valid; otherwise, <code>FALSE</code>.
   */
    bool hasValidOrdering() const { return getOrderingTraversalNum() > getModificationTraversalNum(); }

  /** 
   * Gets the memory manager used by CFG to allocate nodes and edges.
   * 
   * @return The memory manager for given CFG.
   */
    MemoryManager& getMemoryManager() const {return mm;}

  /** 
   * Splits the <code>Return</code> node in CFG, that is creates a new 
   * <code>Block</code> node before the <code>Return</code> node and retarget
   * all incoming edges from the <code>Return</code> node to a new 
   * <code>Block</code> node.
   * After this method call the <code>Return</code> node has only one incoming 
   * edge.
   *
   * @param[in] headerInst  - the instruction to add to a new node
   * 
   * @return The newly created node.
   */
    Node* splitReturnNode(CFGInst* headerInst=NULL) {return splitNode(getReturnNode(), false, headerInst);}

  /** 
   * Splits a node at a particular instruction, leaving the instruction in the
   * same node and moving all instructions before or after the instruction 
   * to a newly created node.
   *
   * @param[in] inst         - the place where to split the node
   * @param[in] splitAfter   - indicates whether to split should appear after 
   *                           <code>TRUE</code> or before
   *                           <code>FLASE</code> instruction
   * @param[in] keepDispatch - indicates if both nodes must have the same dispatch 
   *                           as the <code>Initial</code> node had
   *                           If <code>FLASE</code> the <code>Dispatch</code> node 
   *                           is moved to the node with a higher post-num.
   * 
   * @return The newly created node.
   */
    Node* splitNodeAtInstruction(CFGInst *inst, bool splitAfter, bool keepDispatch, CFGInst* headerInst);

  /** 
   * Creates a new node and targets the edge to it. The old edge target is
   * connected with a new node by new edge after the given method call.
   *
   * @param[in] edge - the edge to splice
   * @param[in] inst - the instruction to add to a new node
   * @param[in] keepOldEdge  - keep old edge and use it to connect source and new nodes
   *
   * @return The newly created node.
   */
    Node* spliceBlockOnEdge(Edge* edge, CFGInst* inst = NULL, bool keepOldEdge=false);

  /** 
   * Inlines <code>inlineFG</code> into this CFG after <code>instAfter</code>, 
   * splits the <code>Instruction</code> node if needed.
   * Moves all nodes from <code>inlineFG</code> except the <code>Exit</code> 
   * node to given CFG.
   * Relies on valid <code>Return</code> and <code>Unwind</code> nodes of 
   * <code>inlinedFG</code>.
   *
   * @param[in] instAfter    - the place to inline. <code>inlinedFG</code> is 
   *                           inlined after this instruction
   * @param[in] inlineFG     - the flow graph to inline. Must have valid unwind 
   *                           and return nodes
   */
    void spliceFlowGraphInline(CFGInst* instAfter, ControlFlowGraph& inlineFG);
    
  /** 
   * Inlines <code>inlineFG</code> info given CFG retargeting the edge to the 
   * <code>inlinedFG</code>'s <code>Entry</code> node.
   * Moves all nodes from <code>inlinedFG</code> except the <code>Exit</code> 
   * node to <code>This</code> CFG.
   * Relies on valid <code>Return</code> and <code>Unwind</code> nodes of the 
   * <code>inlinedFG</code>.
   *
   * @param[in] edge     - the edge to splice the inlined flow graph on.
   * @param[in] inlineFG - the flow graph to inline. Must have valid 
   *                       <code>Return</code> and <code>Unwind</code> nodes.
   */
    void spliceFlowGraphInline(Edge* edge, ControlFlowGraph& inlineFG);


  /** 
   * Removes all critical edges from the graph.
   * Does not split exception edges unless the parameter is <code>TRUE</code>.
   *
   * @param[in] includeExceptionEdges - process exception edges if <code>TRUE</code>
   * @param[in] newNodes              - all newly created nodes
   */
    void splitCriticalEdges(bool includeExceptionEdges, Nodes* newNodes = NULL);

  /** 
   * Moves instructions from one node to another.
   * 
   * @param[in] fromNode - the node to move instructions from
   * @param[in] toNode   - the node to move instructions to
   * @param[in] prepend  - prepends instructions to a new node if <code>TRUE</code>;
   *                       appends instructions if <code>FALSE</code>
   */
    void moveInstructions(Node* fromNode, Node* toNode, bool prepend);

    
  /**  
   * Combines nodes from CFG that can be folded together.
   *
   * @param[in] skipEntry       - does not process the <code>Entry</code> node
   * @param[in] mergeByDispatch - allows merging of nodes with the same dispatch 
   *                              edge target
   */
    void mergeAdjacentNodes(bool skipEntry = false, bool mergeByDispatch= false);

  /**  
   * Combines blocks.
   *
   * @param[in] first     - the first block to merge
   * @param[in] second    - the second block to merger
   * @param[in] keepFirst - tells whether to keep the first or second block
   */
    void mergeBlocks(Node* first, Node* second, bool keepFirst=true);

  /** 
   * Removes all empty nodes from CFG.
   * 
   * @param[in] preserveCriticalEdges  - informs if to preserve critical edges
   * @param[in] removeEmptyCatchBlocks - allows the removal of empty catch blocks 
   *                                     if <code>TRUE</code>
   */
    void purgeEmptyNodes(bool preserveCriticalEdges = false, bool removeEmptyCatchBlocks = false);

  /** 
   * Removes all unreachable nodes from CFG. 
   * If a path connects the node with the <code>Entry</code> node, the node is 
   * reachable.
   */
    void purgeUnreachableNodes() { purgeUnreachableNodes((Nodes*) NULL); }

  /**  
   * Removes all unreachable nodes from CFG and adds them to the container.
   * 
   * @param[in] container - the collection supports the <code>push_back</code>  
   *                        method to store pointers to all removed nodes 
   *                    
   */
    template <class Container> 
        void purgeUnreachableNodes(Container& container) { purgeUnreachableNodes(&container);}


  /**
   * Gets the dominator tree. Updates the tree, if it is in the up-to-date state.
   * 
   * @return The dominator tree; <code>NULL</code> if none dominator tree is 
   *         assigned to the given graph.
   */
    DominatorTree* getDominatorTree() const {return domTree;}

  /** 
   * Gets the post-dominator tree. Updates the tree, if it is in the up-to-date 
   * state.
   * 
   * @return The post-dominator tree; <code>NULL</code> if none post-dominator
   *         tree is assigned to the given graph.
   */
    DominatorTree* getPostDominatorTree() const {return postDomTree;}

  /** 
   * Gets the loop tree. Updates the tree, if it is in the up-to-date state.
   * 
   * @return The loop tree; <code>NULL</code> if none loop tree is
   *         assigned to the given graph.
   */
    LoopTree* getLoopTree() const {return loopTree;}

  /** 
   * Assigns the dominator tree to the graph.
   *
   * param dom - the dominator tree assigned to the graph
   */
    void setDominatorTree(DominatorTree* dom) {domTree = dom;}

  /** 
   * Assigns the post-dominator tree to the graph.
   * 
   * @param[in] dom - the post-dominator tree assigned to the graph
   */
    void setPostDominatorTree(DominatorTree* dom) {domTree = dom;}

  /** 
   * Assigns the loop tree to the graph.
   * 
   * param dom - the loop tree assigned to the graph
   */
    void setLoopTree(LoopTree* lt) {loopTree= lt;}
   
protected:
  /** 
   * Adds the node to the graph nodes list. 
   * Assigns new ID to the node, increments the graph modification count.
   */
    void addNode(Node* node);

  /** 
   * Adds the edge to the graph and connects <code>Source</code> and 
   * <code>Target</code> nodes with this edge.
   * Assigns a new edge ID to the edge, increments the graph modification 
   * count.
   */
    void addEdge(Node* source, Node* target, Edge* edge, double edgeProb);
    
  /** 
   * Removes the node from the graph.
   * 
   * @param[in] i     - the location of the node in the graph node collection
   * @param[in] erase - informs whether to erase or just <code>NULL</code> the 
   *                    pointer to the node in the collection
   */
    void removeNode(Nodes::iterator i, bool erase);

  /** 
   * Sets a new ID to the edge.
   */
    void setNewEdgeId(Edge* edge) { edge->setId(edgeIDGenerator++); }

  /** 
   * Moves all incoming edges from <code>oldNode</code> to 
   * <code>newNode</code>. 
   * Increments modification traversal number of the graph.
   */
    void moveInEdges(Node* oldNode, Node* newNode);

  /** 
   * Moves all outgoing edges from <code>oldNode</code> to 
   * <code>newNode</code>. 
   * Increments modification traversal number of the graph.
   */
    void moveOutEdges(Node* oldNode, Node* newNode);
    
  /** 
   * Removes duplicate incoming edges.
   */
    void resetInEdges(Node* node);
    
  /** 
   * Removes duplicate outgoing edges.
   */
    void resetOutEdges(Node* node);

  /** 
   * Splits the node: adds a new block before or after the node.
   * 
   * @warning Low-level helper method.
   * @warning If <code>newBlockAtEnd</code> is <code>TRUE</code>, the given method does not 
   *          keep dispatch on the original block.
   * @warning Does not move instructions.
   */
    Node* splitNode(Node* node, bool newBlockAtEnd, CFGInst* newBlockInst);

  /// Splits the edge and adds <code>newBlockInst</code> to a new node.
   
    Node* splitEdge(Edge* edge, CFGInst* newBlockInst, bool keepOldEdge);
    
  /// Checks whether the <code>Source</code> node can be merged with the <code>Target</code> node.
   
    bool isBlockMergeAllowed(Node* source, Node* target, bool allowMergeDispatch) const;

  /// Helper for public <code>getNodesPre/PostOrder</code> methods above.
   
    template <class Container>
    void runDFS(Container* preOrderContainer, Container* postOrderContainer, bool isForward) {
        Node* startNode;
        traversalNumber++;
        if (isForward) {
            lastOrderingTraversalNumber = traversalNumber;
            postOrderCache.clear();
            if (entryNode==NULL) {
                return;
            }
            startNode = entryNode;
        } else {
            if (exitNode==NULL) {
                return;
            }
            startNode = exitNode;
        }
        currentPreNumber = currentPostNumber = 0;
        getNodesDFS(preOrderContainer, postOrderContainer, startNode, isForward);
        assert(currentPreNumber == currentPostNumber);
        if (isForward) {
            nodeCount = currentPreNumber;
        } else {
            // getNodesDFS changes traversalNum for nodes. But traversalNum assumes direct traversal.
            // so drop the ordering number here to force CFG recompute ordering before using node->traversalNum values again
            lastOrderingTraversalNumber = lastModifiedTraversalNumber-1;
        }
    }
    
  /// Helper for public <code>getNodesPre/PostOrder</code> methods above. Warn: increment cfg traversal num before use.
   
    template <class Container>
    void getNodesDFS(Container* preOrderContainer, Container* postOrderContainer, Node* node, bool isForward=true) {
        U_32 marked = traversalNumber;
        node->setTraversalNum(marked);
        if(isForward) {
            node->dfNumber = currentPreNumber;
        }
        node->preNumber = currentPreNumber++;
        if(preOrderContainer != NULL) {
            preOrderContainer->push_back(node);
        }
        Edges::const_iterator i = node->getEdges(isForward).begin(), iend = node->getEdges(isForward).end();
        for(; i != iend; i++) {
            Edge* edge = *i;
            Node* succ = edge->getNode(isForward);
            if(succ->getTraversalNum() < marked) {
                getNodesDFS(preOrderContainer, postOrderContainer, succ, isForward);
            }
        }
        node->postNumber = currentPostNumber++;
        if (postOrderContainer != NULL) {
            postOrderContainer->push_back(node);
        }
        if (isForward) {
            postOrderCache.push_back(node);
        }
    }

  /// Removes all nodes unreachable from the entry. 
   
    template <class Container>
        void purgeUnreachableNodes(Container* container) {
            if(!hasValidOrdering()) {
                orderNodes();
            }

            Nodes::iterator iter = nodes.begin(), end = nodes.end();
            for(; iter != end;) {
                Nodes::iterator current = iter;
                Node* node = *iter;
                ++iter;
                if(node->traversalNumber < traversalNumber) {
                    removeNode(current, false);
                    if(container != NULL) {
                        container->push_back(node);
                    }
                }
            }
            nodes.erase(std::remove(nodes.begin(), nodes.end(), (Node*)NULL), nodes.end());
        }

    /// The memory manager used by <code>ControlFlowGraph</code> to allocate its data.
    MemoryManager& mm;
    /// The factory used by <code>ControlFlowGraph</code> to create nodes and edges.
    ControlFlowGraphFactory* factory;
    /// The unique <code>Entry</code> node in <code>ControlFlowGraph</code>.
    Node* entryNode;
    /// The unique <code>Return</code> node in <code>ControlFlowGraph</code>.
    Node* returnNode;
    /// The unique <code>Exit</code> node in <code>ControlFlowGraph</code>.
    Node* exitNode;
    /// The unique <code>Unwind</code> node in <code>ControlFlowGraph</code>.
    Node* unwindNode;
    
    /// The collection of nodes. The order of nodes in the collection is not specified.
    Nodes nodes;
    /// The collection of postordered nodes, which is updated every time the graph is ordered.
    Nodes postOrderCache;

    /// The ID generator for nodes, which is incremented every time a new node is added to the graph.
    U_32 nodeIDGenerator;
    /// The ID generator for edges, which is incremented every time a new edge is added to the graph.
    U_32 edgeIDGenerator;
    /// The number of reachable nodes in the graph, which is updated every time the graph is ordered.
    U_32 nodeCount;
    /// The last graph traversal number used to track graph modifications.
    U_32 traversalNumber;
    /// The given field is assigned to the <code>traversalNumber</code> value every time the graph is modified.
    U_32 lastModifiedTraversalNumber;
    /// The given field is assigned to the <code>traversalNumber</code> value every time the graph is ordered.
    U_32 lastOrderingTraversalNumber;
    /// The given field is assigned to the <code>traversalNumber</code> value every time any edge is removed from the graph.
    U_32 lastEdgeRemovalTraversalNumber;
    /// The given field is assigned to the <code>traversalNumber</code> value every time the profile information is recalculated.
    U_32 lastProfileUpdateTraversalNumber;

    /// The temporary field used by ordering algorithms.
    U_32 currentPreNumber;
    /// The temporary field used by ordering algorithms.
    U_32 currentPostNumber;

    /// Tells whether the graph is annotated with the edge profile.
    bool annotatedWithEdgeProfile;

    /// The dominator tree for the graph. <code>NULL</code> if no dominator tree was set.
    DominatorTree* domTree;
    /// The post-dominator tree for the graph. <code>NULL</code> if no post-dominator tree was set.
    DominatorTree* postDomTree;
    /// The loop tree for the graph. <code>NULL</code> if no loop tree was set.
    LoopTree* loopTree;
};


} //namespace Jitrino 

#endif // _CONTROLFLOWGRAPH_