ROSE 0.11.145.357
Classes | Public Types | Public Member Functions | Public Attributes | Protected Member Functions | Protected Attributes | List of all members
Backstroke::CFG< CFGNodeFilter > Class Template Reference

Description

template<class CFGNodeFilter>
class Backstroke::CFG< CFGNodeFilter >

A class holding a Control Flow Graph.

Definition at line 115 of file graphTemplate.h.

#include <midend/astProcessing/graphTemplate.h>

Inheritance diagram for Backstroke::CFG< CFGNodeFilter >:
Inheritance graph
[legend]
Collaboration diagram for Backstroke::CFG< CFGNodeFilter >:
Collaboration graph
[legend]

Classes

struct  EdgeCopier
 This class is used to copy edges when calling copy_graph(). More...
 
struct  VertexCopier
 This class is used to copy vertices when calling copy_graph(). More...
 

Public Types

typedef VirtualCFG::FilteredCFGNode< CFGNodeFilter > CFGNodeType
 
typedef VirtualCFG::FilteredCFGEdge< CFGNodeFilter > CFGEdgeType
 
typedef boost::shared_ptr< CFGNodeType > CFGNodePtr
 
typedef boost::shared_ptr< CFGEdgeType > CFGEdgePtr
 
typedef GraphTraits::vertex_descriptor Vertex
 
typedef GraphTraits::edge_descriptor Edge
 
typedef std::map< Vertex, Vertex > VertexVertexMap
 

Public Member Functions

std::map< CFGNodeType, Vertex > getNodeVert ()
 
 CFG ()
 The default constructor.
 
 CFG (SgFunctionDefinition *funcDef)
 The constructor building the CFG.
 
void build (SgFunctionDefinition *funcDef)
 Build the actual CFG for the given function.
 
SgFunctionDefinition * getFunctionDefinition () const
 Get the function definition of this CFG.
 
const Vertex & getEntry () const
 Get the entry node of the CFG.
 
const Vertex & getExit () const
 Get the exit node of the CFG.
 
const VertexVertexMap & getDominatorTree ()
 Build the dominator tree of this CFG.
 
const VertexVertexMap & getPostdominatorTree ()
 Build the postdominator tree of this CFG.
 
CFG< CFGNodeFilter > makeReverseCopy () const
 Build a reverse CFG.
 
void toDot (const std::string &filename) const
 Output the graph to a DOT file.
 
std::vector< CFGNodePtr > getAllNodes () const
 Get all CFG nodes in this graph.
 
std::vector< CFGEdgePtr > getAllEdges () const
 Get all CFG edges in this graph.
 
Vertex getVertexForNode (const CFGNodeType &node) const
 Given a CFG node, returns the corresponding vertex in the graph.
 
bool isReducible () const
 Return if this CFG is reducible (if all loops are natural loops, the CFG is reducible).
 
std::vector< Edge > getAllBackEdges ()
 Get all back edges in the CFG. A back edge is one whose target dominates its source.
 
std::vector< Vertex > getAllLoopHeaders ()
 Get all loop headers in this CFG. A natural loop only has one header.
 

Public Attributes

Vertex entry_
 The entry node.
 
Vertex exit_
 The exit node.
 

Protected Member Functions

void buildCFG (const CFGNodeType &node, std::map< CFGNodeType, Vertex > &nodesAdded, std::set< CFGNodeType > &nodesProcessed)
 A internal funtion which builds the actual CFG (boost::graph).
 
void setEntryAndExit ()
 Find the entry and exit of this CFG and set the corresponding members.
 
void writeGraphNode (std::ostream &out, const Vertex &node) const
 This function helps to write the DOT file for vertices.
 
void writeGraphEdge (std::ostream &out, const Edge &edge) const
 This function helps to write the DOT file for edges.
 

Protected Attributes

SgFunctionDefinition * funcDef_
 The function definition of this CFG.
 
std::map< CFGNodeType, Vertex > nodesToVertices_
 A map from a CFG node to the corresponding vertex.
 
VertexVertexMap dominatorTree_
 The dominator tree of this CFG.
 
VertexVertexMap postdominatorTree_
 The postdominator tree of this CFG.
 

Member Typedef Documentation

◆ CFGNodeType

template<class CFGNodeFilter >
typedef VirtualCFG::FilteredCFGNode<CFGNodeFilter> Backstroke::CFG< CFGNodeFilter >::CFGNodeType

Definition at line 122 of file graphTemplate.h.

◆ CFGEdgeType

template<class CFGNodeFilter >
typedef VirtualCFG::FilteredCFGEdge<CFGNodeFilter> Backstroke::CFG< CFGNodeFilter >::CFGEdgeType

Definition at line 123 of file graphTemplate.h.

◆ CFGNodePtr

template<class CFGNodeFilter >
typedef boost::shared_ptr<CFGNodeType> Backstroke::CFG< CFGNodeFilter >::CFGNodePtr

Definition at line 125 of file graphTemplate.h.

◆ CFGEdgePtr

template<class CFGNodeFilter >
typedef boost::shared_ptr<CFGEdgeType> Backstroke::CFG< CFGNodeFilter >::CFGEdgePtr

Definition at line 126 of file graphTemplate.h.

◆ Vertex

template<class CFGNodeFilter >
typedef GraphTraits::vertex_descriptor Backstroke::CFG< CFGNodeFilter >::Vertex

Definition at line 128 of file graphTemplate.h.

◆ Edge

template<class CFGNodeFilter >
typedef GraphTraits::edge_descriptor Backstroke::CFG< CFGNodeFilter >::Edge

Definition at line 129 of file graphTemplate.h.

◆ VertexVertexMap

template<class CFGNodeFilter >
typedef std::map<Vertex, Vertex> Backstroke::CFG< CFGNodeFilter >::VertexVertexMap

Definition at line 131 of file graphTemplate.h.

Constructor & Destructor Documentation

◆ CFG() [1/2]

template<class CFGNodeFilter >
Backstroke::CFG< CFGNodeFilter >::CFG ( )
inline

The default constructor.

Definition at line 160 of file graphTemplate.h.

◆ CFG() [2/2]

template<class CFGNodeFilter >
Backstroke::CFG< CFGNodeFilter >::CFG ( SgFunctionDefinition *  funcDef)
inlineexplicit

The constructor building the CFG.

Definition at line 168 of file graphTemplate.h.

References Backstroke::CFG< CFGNodeFilter >::build().

Member Function Documentation

◆ getNodeVert()

template<class CFGNodeFilter >
std::map< CFGNodeType, Vertex > Backstroke::CFG< CFGNodeFilter >::getNodeVert ( )
inline

Definition at line 155 of file graphTemplate.h.

◆ build()

template<class CFGNodeFilter >
void Backstroke::CFG< CFGNodeFilter >::build ( SgFunctionDefinition *  funcDef)

Build the actual CFG for the given function.

Definition at line 287 of file graphTemplate.h.

References SgNode::cfgForBeginning().

Referenced by Backstroke::CFG< CFGNodeFilter >::CFG().

◆ getFunctionDefinition()

template<class CFGNodeFilter >
SgFunctionDefinition * Backstroke::CFG< CFGNodeFilter >::getFunctionDefinition ( ) const
inline

Get the function definition of this CFG.

Definition at line 180 of file graphTemplate.h.

References Backstroke::CFG< CFGNodeFilter >::funcDef_.

◆ getEntry()

template<class CFGNodeFilter >
const Vertex & Backstroke::CFG< CFGNodeFilter >::getEntry ( ) const
inline

Get the entry node of the CFG.

Definition at line 184 of file graphTemplate.h.

References Backstroke::CFG< CFGNodeFilter >::entry_.

◆ getExit()

template<class CFGNodeFilter >
const Vertex & Backstroke::CFG< CFGNodeFilter >::getExit ( ) const
inline

Get the exit node of the CFG.

Definition at line 188 of file graphTemplate.h.

References Backstroke::CFG< CFGNodeFilter >::exit_.

◆ getDominatorTree()

template<class CFGNodeFilter >
const CFG< CFGNodeFilter >::VertexVertexMap & Backstroke::CFG< CFGNodeFilter >::getDominatorTree ( )

Build the dominator tree of this CFG.

Returns
A map from each node to its immediate dominator.

Definition at line 403 of file graphTemplate.h.

◆ getPostdominatorTree()

template<class CFGNodeFilter >
const CFG< CFGNodeFilter >::VertexVertexMap & Backstroke::CFG< CFGNodeFilter >::getPostdominatorTree ( )

Build the postdominator tree of this CFG.

Definition at line 416 of file graphTemplate.h.

◆ makeReverseCopy()

template<class CFGNodeFilter >
CFG< CFGNodeFilter > Backstroke::CFG< CFGNodeFilter >::makeReverseCopy ( ) const

Build a reverse CFG.

Definition at line 429 of file graphTemplate.h.

References Backstroke::CFG< CFGNodeFilter >::entry_, and Backstroke::CFG< CFGNodeFilter >::exit_.

◆ toDot()

template<class CFGNodeFilter >
void Backstroke::CFG< CFGNodeFilter >::toDot ( const std::string &  filename) const

Output the graph to a DOT file.

Definition at line 278 of file graphTemplate.h.

◆ getAllNodes()

template<class CFGNodeFilter >
std::vector< typename CFG< CFGNodeFilter >::CFGNodePtr > Backstroke::CFG< CFGNodeFilter >::getAllNodes ( ) const

Get all CFG nodes in this graph.

Definition at line 446 of file graphTemplate.h.

◆ getAllEdges()

template<class CFGNodeFilter >
std::vector< typename CFG< CFGNodeFilter >::CFGEdgePtr > Backstroke::CFG< CFGNodeFilter >::getAllEdges ( ) const

Get all CFG edges in this graph.

Definition at line 468 of file graphTemplate.h.

◆ getVertexForNode()

template<class CFGNodeFilter >
CFG< CFGNodeFilter >::Vertex Backstroke::CFG< CFGNodeFilter >::getVertexForNode ( const CFGNodeType &  node) const

Given a CFG node, returns the corresponding vertex in the graph.

Returns Vertex::null_vertex() if the given node is not in the graph

Definition at line 477 of file graphTemplate.h.

◆ isReducible()

template<class CFGNodeFilter >
bool Backstroke::CFG< CFGNodeFilter >::isReducible ( ) const
inline

Return if this CFG is reducible (if all loops are natural loops, the CFG is reducible).

Definition at line 216 of file graphTemplate.h.

◆ getAllBackEdges()

template<class CFGNodeFilter >
std::vector< typename CFG< CFGNodeFilter >::Edge > Backstroke::CFG< CFGNodeFilter >::getAllBackEdges ( )

Get all back edges in the CFG. A back edge is one whose target dominates its source.

Definition at line 490 of file graphTemplate.h.

◆ getAllLoopHeaders()

template<class CFGNodeFilter >
std::vector< typename CFG< CFGNodeFilter >::Vertex > Backstroke::CFG< CFGNodeFilter >::getAllLoopHeaders ( )

Get all loop headers in this CFG. A natural loop only has one header.

Definition at line 519 of file graphTemplate.h.

◆ buildCFG()

template<class CFGNodeFilter >
void Backstroke::CFG< CFGNodeFilter >::buildCFG ( const CFGNodeType &  node,
std::map< CFGNodeType, Vertex > &  nodesAdded,
std::set< CFGNodeType > &  nodesProcessed 
)
protected

A internal funtion which builds the actual CFG (boost::graph).

Definition at line 340 of file graphTemplate.h.

◆ setEntryAndExit()

template<class CFGNodeFilter >
void Backstroke::CFG< CFGNodeFilter >::setEntryAndExit ( )
protected

Find the entry and exit of this CFG and set the corresponding members.

Definition at line 311 of file graphTemplate.h.

◆ writeGraphNode()

template<class CFGNodeFilter >
void Backstroke::CFG< CFGNodeFilter >::writeGraphNode ( std::ostream &  out,
const Vertex &  node 
) const
inlineprotected

This function helps to write the DOT file for vertices.

Definition at line 235 of file graphTemplate.h.

◆ writeGraphEdge()

template<class CFGNodeFilter >
void Backstroke::CFG< CFGNodeFilter >::writeGraphEdge ( std::ostream &  out,
const Edge &  edge 
) const
inlineprotected

This function helps to write the DOT file for edges.

Definition at line 242 of file graphTemplate.h.

Member Data Documentation

◆ entry_

template<class CFGNodeFilter >
Vertex Backstroke::CFG< CFGNodeFilter >::entry_

The entry node.

Definition at line 133 of file graphTemplate.h.

Referenced by Backstroke::CFG< CFGNodeFilter >::getEntry(), and Backstroke::CFG< CFGNodeFilter >::makeReverseCopy().

◆ exit_

template<class CFGNodeFilter >
Vertex Backstroke::CFG< CFGNodeFilter >::exit_

The exit node.

Definition at line 136 of file graphTemplate.h.

Referenced by Backstroke::CFG< CFGNodeFilter >::getExit(), and Backstroke::CFG< CFGNodeFilter >::makeReverseCopy().

◆ funcDef_

template<class CFGNodeFilter >
SgFunctionDefinition* Backstroke::CFG< CFGNodeFilter >::funcDef_
protected

The function definition of this CFG.

Definition at line 142 of file graphTemplate.h.

Referenced by Backstroke::CFG< CFGNodeFilter >::getFunctionDefinition().

◆ nodesToVertices_

template<class CFGNodeFilter >
std::map<CFGNodeType, Vertex> Backstroke::CFG< CFGNodeFilter >::nodesToVertices_
protected

A map from a CFG node to the corresponding vertex.

Definition at line 146 of file graphTemplate.h.

◆ dominatorTree_

template<class CFGNodeFilter >
VertexVertexMap Backstroke::CFG< CFGNodeFilter >::dominatorTree_
protected

The dominator tree of this CFG.

Definition at line 149 of file graphTemplate.h.

◆ postdominatorTree_

template<class CFGNodeFilter >
VertexVertexMap Backstroke::CFG< CFGNodeFilter >::postdominatorTree_
protected

The postdominator tree of this CFG.

Definition at line 152 of file graphTemplate.h.

The documentation for this class was generated from the following file:
Generated on Mon Nov 3 2025 05:40:18 for ROSE by doxygen 1.9.8