ROSE  0.11.145.0
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 17 of file CfgPath.h.

#include <Rose/BinaryAnalysis/Partitioner2/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...
 
typedef Sawyer::Attribute::Storage< Sawyer::SingleThreadedTagAttributes
 Stores user-defined attributes. 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 (ControlFlowGraph::ConstEdgeIterator edge)
 Append a new edge to the end of the path. More...
 
void pushBack (const std::vector< ControlFlowGraph::ConstEdgeIterator > &edges)
 Append a new edge to the end of the path. More...
 
void pushFront (ControlFlowGraph::ConstEdgeIterator edge)
 Insert a new edge to the front of the path. More...
 
void pushFront (const std::vector< ControlFlowGraph::ConstEdgeIterator > &edges)
 Insert 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...
 
std::pair< size_t, size_t > lastInsnIndex (SgAsmInstruction *) const
 Find indices of last vertex and instruction. More...
 
uint64_t hash () const
 Hash the path. More...
 
uint64_t hash (SgAsmInstruction *) const
 Hash part of a path,. More...
 
void print (std::ostream &out) const
 Print the path. More...
 
AttributesvertexAttributes (size_t)
 User-defined attributes for the nth vertex. More...
 
const AttributesvertexAttributes (size_t) const
 User-defined attributes for the nth vertex. More...
 
AttributesedgeAttributes (size_t)
 User-defined attributes for the nth edge. More...
 
const AttributesedgeAttributes (size_t) const
 User-defined attributes for the nth edge. More...
 
size_t nCalls (const FunctionPtr &) const
 Number of function calls. More...
 
size_t nCalls () const
 Number of function calls. More...
 
size_t nReturns (const FunctionPtr &) const
 Number of function returns. More...
 
size_t nReturns () const
 Number of function returns. More...
 
ssize_t callDepth (const FunctionPtr &) const
 Call depth. More...
 
ssize_t callDepth () const
 Call depth. More...
 
size_t maxCallDepth (const FunctionPtr &) const
 Maximum call depth. More...
 
size_t maxCallDepth () const
 Maximum call depth. 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 20 of file CfgPath.h.

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

Stack of vertices.

Definition at line 23 of file CfgPath.h.

Stores user-defined attributes.

Definition at line 26 of file CfgPath.h.

Constructor & Destructor Documentation

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

Construct an empty path.

Definition at line 44 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 47 of file CfgPath.h.

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

Construct a path given an initial edge.

Definition at line 51 of file CfgPath.h.

Member Function Documentation

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

Makes this path empty.

Definition at line 55 of file CfgPath.h.

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

Determine if a path is empty.

Definition at line 64 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 77 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 84 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 91 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 99 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 107 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 ( 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. The specified edge is pushed onto the path and the path is configured to visit the sibling edges during the backtrack operation in order by incrementing the given iterator.

void Rose::BinaryAnalysis::Partitioner2::CfgPath::pushBack ( const std::vector< ControlFlowGraph::ConstEdgeIterator > &  edges)

Append a new edge to the end of the path.

The argument is a list of edges all originating from the same vertex. If the path is non-empty, then the originating vertex must be equal to the backVertex. The argument specifies the order in which the backtrack operation will visit the edges, and only the first edge of this list is actually appended to the path.

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

Insert 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. The specified edge is inserted at the front of the path and the path is configured to visit the sibling edges during the backtrack operation in order by incrementing the given iterator.

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::pushFront ( const std::vector< ControlFlowGraph::ConstEdgeIterator > &  edges)

Insert a new edge to the front of the path.

The argument is a list of edges all pointing to the same vertex. If the path is non-empty, then the pointed to vertex must be equal to frontVertex. The argument specifies the order in which the backtrack operation will visit the edges, and only the first edge of this list is actually inserted at the front 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.

Attributes& Rose::BinaryAnalysis::Partitioner2::CfgPath::vertexAttributes ( size_t  )

User-defined attributes for the nth vertex.

Each vertex in the path has a corresponding attribute storage system. The attribute storage lifetime is the same as that of the vertex to which it corresponds; when the path through the vertex index changes, the storage is reset. Note that there is always one more vertex than edge (except when the path is completely empty). Edge number i has two endpoints that are vertices i and i+1.

const Attributes& Rose::BinaryAnalysis::Partitioner2::CfgPath::vertexAttributes ( size_t  ) const

User-defined attributes for the nth vertex.

Each vertex in the path has a corresponding attribute storage system. The attribute storage lifetime is the same as that of the vertex to which it corresponds; when the path through the vertex index changes, the storage is reset. Note that there is always one more vertex than edge (except when the path is completely empty). Edge number i has two endpoints that are vertices i and i+1.

Attributes& Rose::BinaryAnalysis::Partitioner2::CfgPath::edgeAttributes ( size_t  )

User-defined attributes for the nth edge.

Each edge in the path has a corresponding attribute storage system. The attribute storage lifetime is the same as that of the edge to which it corresponds; when the path through the edge index changes, the storage is reset. Note that there is always one more vertex than edge (except when the path is completely empty). Edge number i has two endpoints that are vertices i and i+1.

const Attributes& Rose::BinaryAnalysis::Partitioner2::CfgPath::edgeAttributes ( size_t  ) const

User-defined attributes for the nth edge.

Each edge in the path has a corresponding attribute storage system. The attribute storage lifetime is the same as that of the edge to which it corresponds; when the path through the edge index changes, the storage is reset. Note that there is always one more vertex than edge (except when the path is completely empty). Edge number i has two endpoints that are vertices i and i+1.

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 FunctionPtr ) 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::nCalls ( ) 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 FunctionPtr ) 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.

size_t Rose::BinaryAnalysis::Partitioner2::CfgPath::nReturns ( ) 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 FunctionPtr ) 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.

ssize_t Rose::BinaryAnalysis::Partitioner2::CfgPath::callDepth ( ) 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 FunctionPtr ) 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.

size_t Rose::BinaryAnalysis::Partitioner2::CfgPath::maxCallDepth ( ) 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.

std::pair<size_t , size_t > Rose::BinaryAnalysis::Partitioner2::CfgPath::lastInsnIndex ( SgAsmInstruction ) const

Find indices of last vertex and instruction.

Given an instruction, return the index of the last occurrence of the instruction in this path. The return value is the index of the vertex containing the last occurrence of the instruction, and the index of the instruction across all instructions and summarized functions in this path. The path must contain at least one occurrence of the specified instruction.

uint64_t Rose::BinaryAnalysis::Partitioner2::CfgPath::hash ( ) const

Hash the path.

The path vertex addresses are hashed in the order they appear in order to create a unique identifier for the path. Any user-defined data attached to the path is not hashed.

uint64_t Rose::BinaryAnalysis::Partitioner2::CfgPath::hash ( SgAsmInstruction ) const

Hash part of a path,.

Hash this path up to and including the last occurrence of the specified instruction. This hash is calculated differently than hash with no arguments, thus even if the specified instruction is the very last instruction of the path the hashes returned by the two functions will differ.

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

Print the path.


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