harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ge...@apache.org
Subject svn commit: r449229 - /incubator/harmony/enhanced/drlvm/trunk/vm/jitrino/src/shared/ControlFlowGraph.h
Date Sat, 23 Sep 2006 13:17:59 GMT
Author: geirm
Date: Sat Sep 23 06:17:59 2006
New Revision: 449229

URL: http://svn.apache.org/viewvc?view=rev&rev=449229
Log:
HARMONY-1544

The patch contains Doxygen documentation for all classes/methods/fields in ControlFlowGraph.h file - the base 
structure for Jitrino IR in both optimizer and codegenerator modules.


Ubuntu 6 - smoke

Modified:
    incubator/harmony/enhanced/drlvm/trunk/vm/jitrino/src/shared/ControlFlowGraph.h

Modified: incubator/harmony/enhanced/drlvm/trunk/vm/jitrino/src/shared/ControlFlowGraph.h
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/drlvm/trunk/vm/jitrino/src/shared/ControlFlowGraph.h?view=diff&rev=449229&r1=449228&r2=449229
==============================================================================
--- incubator/harmony/enhanced/drlvm/trunk/vm/jitrino/src/shared/ControlFlowGraph.h (original)
+++ incubator/harmony/enhanced/drlvm/trunk/vm/jitrino/src/shared/ControlFlowGraph.h Sat Sep 23 06:17:59 2006
@@ -20,8 +20,19 @@
 *
 */
 
+/**
+* @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_
+#define _CONTROLFLOWGRAPH_ 
+
 
 #include <assert.h>
 #include <iostream>
@@ -44,404 +55,1611 @@
 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:
-    enum Kind {                  // shortcut: max1: only one edge of this type/node. maxN: multiple edges/node
-        Kind_Dispatch = 1,       // All *->DN edges.  
-        Kind_Unconditional = 2,  // Jump or fall-through with no branch BN->BN, *->EXIT (max1)
-        Kind_False = 4,          // Fall-through after not-taken branch BN->BN, default target of switches (max1)
-        Kind_True = 8,           // A taken branch BN->BN, switch edges (except default) (maxN)
-        Kind_Catch = 16          // All DN->BN edges  (maxN)
+  /** 
+   * 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() {}
 
 
-    // Get the unique edge ID.  This is unique for all edges in the containing flow graph.
-    // It is constant for the lifetime of this edge.
+  /** 
+   * ID is constant for the lifetime of the edge.
+   *
+   * @return The unique edge ID that is constant for lifetime of this edge.
+   */
     uint32 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;}
 
 
-    //profile info
+  /**
+   * @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(uint32 _id) {id = _id;}
 
+    /// The unique edge ID within CFG.
     uint32 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;
 };
 
+  /** 
+   * 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 {
-friend class Node;
-friend class Edge;
-friend class ControlFlowGraph;
+  /** 
+   * 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;
 
-    // unlinks inst from node
+  /** 
+   * 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 'this' before 'inst'. Assign node to 'this' 
-    // if 'this' inst has next inst, it's also inserted
-    void insertBefore(CFGInst* inst);
-    
-    // inserts 'this' after 'inst'. Assign node to 'this' 
-    // if 'this' inst has next inst, it's also inserted
-    void insertAfter(CFGInst* inst);
-
+  /** 
+   * 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;}
 
 protected:
-    // called from CFG to detect BB->BB block edges
+    /// 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 edge target is replaced
+    /// Called from CFG, when the edge target is replaced.
     virtual void updateControlTransferInst(Node* oldTarget, Node* newTarget) {}
-    // called from CFG when 2 blocks are merging and one of  the branches is redundant.
+    /// 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) {}
+
+    /// The owner node of the instruction.
     Node* node;
 };
 
+  /** 
+   * 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 {
-        Kind_Block,      // Basic block
-        Kind_Dispatch,   // Exception Dispatch
-        Kind_Exit        // Exit
+        /// 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;}
 
-    // Get the unique node ID.  This is unique for all nodes in the containing flow graph.
-    // It is constant for the lifetime of this node.  This provides a sparse id between 0
-    // and the graph's getMaxNodeId().
+  /** 
+   * 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.
+   */
     uint32 getId() const {return id;}
 
-    // Get the depth first numbering of this node computed during the last pass.
-    // Use this number as a dense id during a short phase.
+  /** 
+   * 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.
+   */
     uint32 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.
+   */
     uint32 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.
+   */
     uint32 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;}
-    bool isCatchBlock() const {return getInDegree() >=1 && getInEdges().front()->isCatchEdge();}
-
-    //edges
+    
+  /** 
+   * 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;}
     
-    // Get the first edge that matches this kind.  
-    // Return NULL if no such edge exists,
+  /** 
+   * 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);}
-    Edge* getExceptionEdge() const {return getOutEdge(Edge::Kind_Dispatch);}
-    bool  isConnectedTo(bool isForward, Node* node) const {return findEdgeTo(isForward, node)!=NULL;}
-    Edge*  findEdgeTo(bool isForward, Node* node) const;
     
-    // return target of the first edge with specified kind found.
-    // return NULL if no edge found with specified kind
+  /** 
+   * 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);}
     
-    // Find the edge corresponding to a particular source or target.  Return NULL if
-    // no such edge is found.
-    Edge* findEdge(bool isForward, const Node* node) const;
+  /** 
+   * 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.
+   */
     uint32 getOutDegree() const {return getOutEdges().size();}
+    
+  /** 
+   * Gets the number of incoming edges to the node. 
+   *
+   * @return The number of incoming edges to the node.
+   */
     uint32 getInDegree() const {return 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;}
 
 
     
-    // insts 
-
-    // appends inst to the end of node list.
-    // if inst is a list of insts (has next insts) -> the whole list is appended
+    
+  /** 
+   * 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);
 
-    // appends inst to the beginning of node list. Checks "block header critical inst" property
-    // if inst is a list of insts (has next insts) -> the whole list is prepended
+  /** 
+   * 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 number of inst in node. Complexity ~ num of insts
+  /** 
+   * 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. 
+   */
     uint32 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;}
 
-    //profile info
+  /** 
+   * 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;}
 
-    //mod count
+
+  /**
+   * Gets the current node traversal number used by internal and external 
+   * algorithms to mark node as visited.
+   *
+   * @return The traversal number for the node.
+   */
     uint32 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(uint32 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;}
 
 protected:
-
-    Node(MemoryManager& mm, Kind _kind);
-    
+  /** 
+   * 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(uint32 _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.
     uint32 id;
+    
+  /** 
+   * The depth-first number of the node in CFG. 
+   * It is updated every time CFG is ordered.
+   */
     uint32 dfNumber;
+
+  /** 
+   * The pre-number of the node in CFG. 
+   * It is updated every time CFG is ordered.
+   */
     uint32 preNumber;
+    
+  /** 
+   * The post-number of the node in CFG. 
+   * It is updated every time CFG is ordered.
+   */
     uint32 postNumber;
+
+  /** 
+   * The number of times the node was traversed by the 
+   * ordering algorithms.
+   * It is updated every time CFG is ordered.
+   */
     uint32 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(){};
     
-    // Return a collection of all nodes in the graph.  The order in the list has no semantic
-    // value.  Note this also returns unreachable nodes.
+  /** 
+   * 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;}
     
-    // Get unique entry node.  This node dominates every other node in the graph.
+  /**  
+   * 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;}
     
-    // Get unique exit node.  This node post-dominates every other node in the graph.
+  /**  
+   * 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;}
 
-    // Get unique exit block node.  
-    // This node post-dominates every other block node in the graph.
+  /** 
+   * 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;}
         
-    // Get unique unwind node.  This node post-dominates every other dispatch node in the graph.
+  /**  
+   * 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(unwindNode==NULL); 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.
+   */
     uint32 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 node and all it's in/out edges
+  /** 
+   * Removes the node and all its incoming and outgoing edges from the graph.
+   * 
+   * @param[in] node - a node to remove 
+   */
     void removeNode(Node* node);
 
-    // Return the number of nodes in the graph that are reachable. Recompute if the graph was modified.
+  /** 
+   * 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.
+   */
     uint32 getNodeCount() { if(!hasValidOrdering()) orderNodes(); return nodeCount; }
     
-    // return cached postorder collection
+  /** 
+   * 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>isForwarisForward</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);
     }
 
-    //edges:
-    //creates new edge from source to target
+  /** 
+   * 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.
+   */
     uint32 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
+   * 
+   * @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 obsolete and should be refactored.
+   *       The only place to take care is retargeting edges 
+   *       while inlining CFG: edge IDs must be renewed.
+   */
     Edge* replaceEdgeTarget(Edge* edge, Node *newTarget);
 
-    // adds unconditional edge for BB->BB,BB->E or dispatch edge for *->DN nodes
-      
-    //profile info
+  /** 
+   * 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;}
-    //check if edge profile is consistent. 
-    //Checks only reachable nodes. Recalculates postorder cache if needed.
+
+
+  /** 
+   * 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);
-    //count node exec count from probs
+    
+  /** 
+   * Counts the execution counts of nodes using edge probabilities and execution 
+   * count of the <code>Entry</code> node.
+   */
     void smoothEdgeProfile();
 
 
-    // The traversal number is analogous to a monotonically increasing timestamp.
-    // It is updated anytime an ordering traversal is performed on the CFG.
-    // If a modification was performed after an ordering, the ordering is invalid.
+  /** 
+   * 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
+   */
     uint32 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(uint32 newTraversalNum) {traversalNumber = newTraversalNum;}
 
-    // The modification traversal number is the traversal number of the
-    // last add/remove of a node/edge in the graph.
+  /** 
+   * 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.
+   */
     uint32 getModificationTraversalNum() const { return lastModifiedTraversalNumber; }
 
-    // The modification traversal number is the traversal number of the
-    // last remove of an edge in the graph.
+  /** 
+   * 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.
+   */
     uint32 getEdgeRemovalTraversalNum() const { return lastEdgeRemovalTraversalNumber; }
 
-    // The ordering traversal number is the traversal number after the last depth
-    // first ordering.  Node pre/postnumbers are valid if
-    // getOrderingTraversalNum() > getModificationTraversalNum().
+  /** 
+   * 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.
+   */
     uint32 getOrderingTraversalNum() const { return lastOrderingTraversalNumber; }
 
-    // Return true if the current ordering is still valid.
+  /** 
+   * 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(); }
 
-    //Memory manager used by graph
+  /** 
+   * 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);}
 
-    // this utility splits a node at a particular instruction, leaving the instruction in the
-    // same node and moving all insts (before inst : splitAfter=false/after inst : splitAfter=true 
-    // to the newly created note
-    // returns the new node created
+  /** 
+   * 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
+   *
+   * @return The newly created node.
+   */
     Node* spliceBlockOnEdge(Edge* edge, CFGInst* inst = NULL);
 
-    // Inline inlineFG info this CFG after 'instAfter' (splits inst's node if needed)
-    // move all nodes from inlinedFG except exit node to 'this' FG
-    // relies on valid 'return' and 'unwind' nodes on inlinedFG
+  /** 
+   * 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
+   * @param[in] keepDispatch - indicates if both nodes after the splitting must  
+   *                           have the same dispatch as the initial node had.
+   *                           If <code>FALSE</code> the <code>Dispatch</code> node 
+   *                           is moved to the node with a higher post-num.
+   */
     void spliceFlowGraphInline(CFGInst* instAfter, ControlFlowGraph& inlineFG, bool keepDispatch=true);
     
-    // Inline inlineFG info this CFG moving egde head to inlinedFG prolog
-    // move all nodes from inlinedFG except exit node to 'this' FG
-    // relies on valid 'return' and 'unwind' nodes on inlinedFG
+  /** 
+   * 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);
 
-    // Remove all critical edges from Graph
-    // Does not split exception edges (edges to Dispatch nodes)
-    // unless parameter is true.
+
+  /** 
+   * 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);
 
     
-    // Combine nodes from CFG that can be folded together.
+  /**  
+   * 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);
 
-    void mergeBlocks(Node* source, Node* target, bool keepFirst=true);
-
-    // Remove all empty nodes from CFG.
+  /**  
+   * 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);
 
-    // Remove all unreachable nodes from CFG,
+  /** 
+   * 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); }
 
-    // Remove all unreachable nodes from CFG.  Add removed nodes to container.
+  /**  
+   * 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);
-    void moveOutEdges(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);
 
-    //low-level helper methods
-    // WARN: this method does not keep dispatch on original block if newBlockAtEnd=true!
-    // WARN: does not move instructions
-    Node* splitNode(Node* node, bool newBlockAtEnd, CFGInst* inst);
-    Node* splitEdge(Edge* edge, CFGInst* inst);
-    bool ControlFlowGraph::isBlockMergeAllowed(Node* source, Node* target, bool allowMergeDispatch) const;
+  /** 
+   * 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);
+    
+  /// 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 getNodesPre/PostOrder above.
+  /// Helper for public <code>getNodesPre/PostOrder</code> methods above.
+   
     template <class Container>
     void runDFS(Container* preOrderContainer, Container* postOrderContainer, bool isForward) {
         Node* startNode;
@@ -460,7 +1678,9 @@
             nodeCount = currentPreNumber;
         }
     }
-    // Helper for getNodesPre/PostOrder above.
+    
+  /// Helper for public <code>getNodesPre/PostOrder</code> methods above.
+   
     template <class Container>
     void getNodesDFS(Container* preOrderContainer, Container* postOrderContainer, Node* node, bool isForward=true) {
         uint32 marked = traversalNumber;
@@ -489,7 +1709,8 @@
         }
     }
 
-    // Remove all nodes unreachable from entry.
+  /// Removes all nodes unreachable from the entry. 
+   
     template <class Container>
         void purgeUnreachableNodes(Container* container) {
             if(!hasValidOrdering()) {
@@ -511,31 +1732,54 @@
             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.
     uint32 nodeIDGenerator;
+    /// The ID generator for edges, which is incremented every time a new edge is added to the graph.
     uint32 edgeIDGenerator;
+    /// The number of reachable nodes in the graph, which is updated every time the graph is ordered.
     uint32 nodeCount;
+    /// The last graph traversal number used to track graph modifications.
     uint32 traversalNumber;
+    /// The given field is assigned to the <code>traversalNumber</code> value every time the graph is modified.
     uint32 lastModifiedTraversalNumber;
+    /// The given field is assigned to the <code>traversalNumber</code> value every time the graph is ordered.
     uint32 lastOrderingTraversalNumber;
+    /// The given field is assigned to the <code>traversalNumber</code> value every time any edge is removed from the graph.
     uint32 lastEdgeRemovalTraversalNumber;
+    /// The given field is assigned to the <code>traversalNumber</code> value every time the profile information is recalculated.
     uint32 lastProfileUpdateTraversalNumber;
+
+    /// The temporaty field used by ordering algorithms.
     uint32 currentPreNumber;
+    /// The temporaty field used by ordering algorithms.
     uint32 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;
 };
 



Mime
View raw message