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;
};
|