ROSE  0.9.9.139
Public Types | Public Member Functions | List of all members
Rose::BinaryAnalysis::Partitioner2::CfgPath Class Reference

Description

A path through a control flow graph.

A CFG path consists of a starting CFG vertex plus zero or more CFG edges. The first edge is an outgoing edge of the starting vertex and subsequent edges must be connected through inter-edge vertices. An empty path is a path with no edges and no starting vertex. A path acts like a stack in that edges can be pushed and popped from the end of the path.

Definition at line 15 of file CfgPath.h.

#include <CfgPath.h>

Public Types

typedef std::vector< ControlFlowGraph::ConstEdgeIterator > Edges
 Stack of inter-connected edges. More...
 
typedef std::vector< ControlFlowGraph::ConstVertexIterator > Vertices
 Stack of vertices. More...
 

Public Member Functions

 CfgPath ()
 Construct an empty path. More...
 
 CfgPath (const ControlFlowGraph::ConstVertexIterator &vertex)
 Construct a path having only a starting vertex. More...
 
 CfgPath (const ControlFlowGraph::ConstEdgeIterator &edge)
 Construct a path given an initial edge. More...
 
void clear ()
 Makes this path empty. More...
 
bool isEmpty () const
 Determine if a path is empty. More...
 
bool isConnected () const
 Verify that path edges are connected. More...
 
size_t nEdges () const
 Number of edges in a path. More...
 
size_t nVertices () const
 Number of vertices in a path. More...
 
ControlFlowGraph::ConstVertexIterator frontVertex () const
 Returns the vertex where the path starts. More...
 
ControlFlowGraph::ConstVertexIterator backVertex () const
 Returns the vertex where the path ends. More...
 
const Edgesedges () const
 Returns all the edges in a path. More...
 
Vertices vertices () const
 Return all the vertices in a path. More...
 
void pushBack (const ControlFlowGraph::ConstEdgeIterator &edge)
 Append a new edge to the end of the path. More...
 
void pushFront (const ControlFlowGraph::ConstEdgeIterator &edge)
 Append a new edge to the front of the path. More...
 
void popBack ()
 Erase the final edge from a path. More...
 
std::vector< ControlFlowGraph::ConstEdgeIterator > backtrack ()
 Backtrack to next path. More...
 
size_t nVisits (const ControlFlowGraph::ConstVertexIterator &vertex) const
 Number of times vertex appears in path. More...
 
size_t nVisits (const ControlFlowGraph::ConstEdgeIterator &edge) const
 Number of times edge appears in path. More...
 
size_t nCalls (const Function::Ptr &function=Function::Ptr()) const
 Number of function calls. More...
 
size_t nReturns (const Function::Ptr &function=Function::Ptr()) const
 Number of function returns. More...
 
ssize_t callDepth (const Function::Ptr &function=Function::Ptr()) const
 Call depth. More...
 
size_t maxCallDepth (const Function::Ptr &function=Function::Ptr()) const
 Maximum call depth. More...
 
void print (std::ostream &out) const
 Print the path. More...
 
std::vector< ControlFlowGraph::ConstEdgeIterator > truncate (const ControlFlowGraph::ConstEdgeIterator &)
 Truncate the path. More...
 
std::vector< ControlFlowGraph::ConstEdgeIterator > truncate (const CfgConstEdgeSet &)
 Truncate the path. More...
 

Member Typedef Documentation

typedef std::vector<ControlFlowGraph::ConstEdgeIterator> Rose::BinaryAnalysis::Partitioner2::CfgPath::Edges

Stack of inter-connected edges.

Definition at line 18 of file CfgPath.h.

typedef std::vector<ControlFlowGraph::ConstVertexIterator> Rose::BinaryAnalysis::Partitioner2::CfgPath::Vertices

Stack of vertices.

Definition at line 21 of file CfgPath.h.

Constructor & Destructor Documentation

Rose::BinaryAnalysis::Partitioner2::CfgPath::CfgPath ( )
inline

Construct an empty path.

Definition at line 29 of file CfgPath.h.

Rose::BinaryAnalysis::Partitioner2::CfgPath::CfgPath ( const ControlFlowGraph::ConstVertexIterator &  vertex)
inlineexplicit

Construct a path having only a starting vertex.

Definition at line 32 of file CfgPath.h.

Rose::BinaryAnalysis::Partitioner2::CfgPath::CfgPath ( const ControlFlowGraph::ConstEdgeIterator &  edge)
inlineexplicit

Construct a path given an initial edge.

Definition at line 35 of file CfgPath.h.

Member Function Documentation

void Rose::BinaryAnalysis::Partitioner2::CfgPath::clear ( )
inline

Makes this path empty.

Definition at line 39 of file CfgPath.h.

bool Rose::BinaryAnalysis::Partitioner2::CfgPath::isEmpty ( ) const
inline

Determine if a path is empty.

Definition at line 45 of file CfgPath.h.

Referenced by backVertex(), frontVertex(), and nVertices().

bool Rose::BinaryAnalysis::Partitioner2::CfgPath::isConnected ( ) const

Verify that path edges are connected.

Checks whether adjacent edges in the path go through a common vertex. Returns true if they do, false otherwise. Returns true for a path with no edges.

size_t Rose::BinaryAnalysis::Partitioner2::CfgPath::nEdges ( ) const
inline

Number of edges in a path.

A path with zero edges is not necessarily empty; it may have an initial vertex.

Definition at line 58 of file CfgPath.h.

Referenced by nVertices().

size_t Rose::BinaryAnalysis::Partitioner2::CfgPath::nVertices ( ) const
inline

Number of vertices in a path.

The number of vertices in a non-empty path is one more than the number of edges. An empty path has zero vertices.

Definition at line 65 of file CfgPath.h.

References isEmpty(), and nEdges().

ControlFlowGraph::ConstVertexIterator Rose::BinaryAnalysis::Partitioner2::CfgPath::frontVertex ( ) const
inline

Returns the vertex where the path starts.

The path must not be empty.

Definition at line 72 of file CfgPath.h.

References isEmpty().

ControlFlowGraph::ConstVertexIterator Rose::BinaryAnalysis::Partitioner2::CfgPath::backVertex ( ) const
inline

Returns the vertex where the path ends.

The path must not be empty.

Definition at line 80 of file CfgPath.h.

References isEmpty().

const Edges& Rose::BinaryAnalysis::Partitioner2::CfgPath::edges ( ) const
inline

Returns all the edges in a path.

A path with no edges is not necessarly an empty path; it may have an initial vertex.

Definition at line 88 of file CfgPath.h.

Vertices Rose::BinaryAnalysis::Partitioner2::CfgPath::vertices ( ) const

Return all the vertices in a path.

The list of vertices is not stored explicitly by this path object and must be recomputed for each call. Vertices are not necessarily unique within a path since they can be reached sometimes by multiple edges.

void Rose::BinaryAnalysis::Partitioner2::CfgPath::pushBack ( const ControlFlowGraph::ConstEdgeIterator &  edge)

Append a new edge to the end of the path.

If the path is not empty then the source vertex for the new edge must be equal to the backVertex.

void Rose::BinaryAnalysis::Partitioner2::CfgPath::pushFront ( const ControlFlowGraph::ConstEdgeIterator &  edge)

Append a new edge to the front of the path.

If the path is not empty, then the target vertex for the new edge must be equal to the frontVertex.

Pushing edges onto the front of a path is not efficient; it requires moving all previous edges, taking time linearly proportional to the length of the path.

void Rose::BinaryAnalysis::Partitioner2::CfgPath::popBack ( )

Erase the final edge from a path.

Erasing the only remaining edge will leave the path in a state where it has only a starting vertex and no edges. Calling this method on such a path will remove the starting vertex. This method should not be called if the path is empty (has no edges and no starting vertex).

std::vector<ControlFlowGraph::ConstEdgeIterator> Rose::BinaryAnalysis::Partitioner2::CfgPath::backtrack ( )

Backtrack to next path.

Pops edges from the path until a vertex is reached where some other (later) edge can be followed, then push that edge onto the path. If no subsequent path through the CFG is available, then modify this path to be empty. This happens when this path's edges are all final outgoing edges for each vertex in the path.

Returns the edges that were removed in the order that they were removed. I.e., the first edge popped from the end of the path is at the front of the returned vector.

size_t Rose::BinaryAnalysis::Partitioner2::CfgPath::nVisits ( const ControlFlowGraph::ConstVertexIterator &  vertex) const

Number of times vertex appears in path.

size_t Rose::BinaryAnalysis::Partitioner2::CfgPath::nVisits ( const ControlFlowGraph::ConstEdgeIterator &  edge) const

Number of times edge appears in path.

size_t Rose::BinaryAnalysis::Partitioner2::CfgPath::nCalls ( const Function::Ptr function = Function::Ptr()) const

Number of function calls.

Counts the number of E_FUNCTION_CALL edges in a path. If a non-null function is supplied then only count those edges that enter the specified function.

size_t Rose::BinaryAnalysis::Partitioner2::CfgPath::nReturns ( const Function::Ptr function = Function::Ptr()) const

Number of function returns.

Counts the number of E_FUNCTION_RETURN edges in a path. If a non-null function is supplied then only count those edges that return from the specified function.

ssize_t Rose::BinaryAnalysis::Partitioner2::CfgPath::callDepth ( const Function::Ptr function = Function::Ptr()) const

Call depth.

Returns the function call depth at the end of the path. The call depth is incremented for each E_FUNCTION_CALL edge and decremented for each E_FUNCTION_RETURN edge, and the value at the end of the path is returned. If a non-null function is specified, then count only calls to that function and returns from that function. The return value may be negative if more return edges than call edges are encountered.

size_t Rose::BinaryAnalysis::Partitioner2::CfgPath::maxCallDepth ( const Function::Ptr function = Function::Ptr()) const

Maximum call depth.

Returns the maximum function call depth in the path. The call depth is incremented for each E_FUNCTION_CALL edge and decremented for each E_FUNCTION_RETURN edge, and its maximum value is returned. If a non-null function is specified, then count only calls to that function and returns from that function.

std::vector<ControlFlowGraph::ConstEdgeIterator> Rose::BinaryAnalysis::Partitioner2::CfgPath::truncate ( const ControlFlowGraph::ConstEdgeIterator &  )

Truncate the path.

Erase edges from the end of this path until this path contains none of the specified edges.

Returns the edges that were removed in the order that they were removed. I.e., the first edge popped from the end of the path is at the front of the returned vector.

std::vector<ControlFlowGraph::ConstEdgeIterator> Rose::BinaryAnalysis::Partitioner2::CfgPath::truncate ( const CfgConstEdgeSet )

Truncate the path.

Erase edges from the end of this path until this path contains none of the specified edges.

Returns the edges that were removed in the order that they were removed. I.e., the first edge popped from the end of the path is at the front of the returned vector.

void Rose::BinaryAnalysis::Partitioner2::CfgPath::print ( std::ostream &  out) const

Print the path.


The documentation for this class was generated from the following file: