|
ROSE 0.11.145.147
|
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.
#include <Rose/BinaryAnalysis/Partitioner2/CfgPath.h>
Public Types | |
| typedef std::vector< ControlFlowGraph::ConstEdgeIterator > | Edges |
| Stack of inter-connected edges. | |
| typedef std::vector< ControlFlowGraph::ConstVertexIterator > | Vertices |
| Stack of vertices. | |
| typedef Sawyer::Attribute::Storage< Sawyer::SingleThreadedTag > | Attributes |
| Stores user-defined attributes. | |
Public Member Functions | |
| CfgPath () | |
| Construct an empty path. | |
| CfgPath (const ControlFlowGraph::ConstVertexIterator &vertex) | |
| Construct a path having only a starting vertex. | |
| CfgPath (const ControlFlowGraph::ConstEdgeIterator &edge) | |
| Construct a path given an initial edge. | |
| void | clear () |
| Makes this path empty. | |
| bool | isEmpty () const |
| Determine if a path is empty. | |
| bool | isConnected () const |
| Verify that path edges are connected. | |
| size_t | nEdges () const |
| Number of edges in a path. | |
| size_t | nVertices () const |
| Number of vertices in a path. | |
| ControlFlowGraph::ConstVertexIterator | frontVertex () const |
| Returns the vertex where the path starts. | |
| ControlFlowGraph::ConstVertexIterator | backVertex () const |
| Returns the vertex where the path ends. | |
| const Edges & | edges () const |
| Returns all the edges in a path. | |
| Vertices | vertices () const |
| Return all the vertices in a path. | |
| void | pushBack (ControlFlowGraph::ConstEdgeIterator edge) |
| Append a new edge to the end of the path. | |
| void | pushBack (const std::vector< ControlFlowGraph::ConstEdgeIterator > &edges) |
| Append a new edge to the end of the path. | |
| void | pushFront (ControlFlowGraph::ConstEdgeIterator edge) |
| Insert a new edge to the front of the path. | |
| void | pushFront (const std::vector< ControlFlowGraph::ConstEdgeIterator > &edges) |
| Insert a new edge to the front of the path. | |
| void | popBack () |
| Erase the final edge from a path. | |
| std::vector< ControlFlowGraph::ConstEdgeIterator > | backtrack () |
| Backtrack to next path. | |
| size_t | nVisits (const ControlFlowGraph::ConstVertexIterator &vertex) const |
| Number of times vertex appears in path. | |
| size_t | nVisits (const ControlFlowGraph::ConstEdgeIterator &edge) const |
| Number of times edge appears in path. | |
| std::pair< size_t, size_t > | lastInsnIndex (SgAsmInstruction *) const |
| Find indices of last vertex and instruction. | |
| uint64_t | hash () const |
| Hash the path. | |
| uint64_t | hash (SgAsmInstruction *) const |
| Hash part of a path,. | |
| void | print (std::ostream &out) const |
| Print the path. | |
| Attributes & | vertexAttributes (size_t) |
| User-defined attributes for the nth vertex. | |
| const Attributes & | vertexAttributes (size_t) const |
| User-defined attributes for the nth vertex. | |
| Attributes & | edgeAttributes (size_t) |
| User-defined attributes for the nth edge. | |
| const Attributes & | edgeAttributes (size_t) const |
| User-defined attributes for the nth edge. | |
| size_t | nCalls (const FunctionPtr &) const |
| Number of function calls. | |
| size_t | nCalls () const |
| Number of function calls. | |
| size_t | nReturns (const FunctionPtr &) const |
| Number of function returns. | |
| size_t | nReturns () const |
| Number of function returns. | |
| ssize_t | callDepth (const FunctionPtr &) const |
| Call depth. | |
| ssize_t | callDepth () const |
| Call depth. | |
| size_t | maxCallDepth (const FunctionPtr &) const |
| Maximum call depth. | |
| size_t | maxCallDepth () const |
| Maximum call depth. | |
| std::vector< ControlFlowGraph::ConstEdgeIterator > | truncate (const ControlFlowGraph::ConstEdgeIterator &) |
| Truncate the path. | |
| std::vector< ControlFlowGraph::ConstEdgeIterator > | truncate (const CfgConstEdgeSet &) |
| Truncate the path. | |
| typedef std::vector<ControlFlowGraph::ConstEdgeIterator> Rose::BinaryAnalysis::Partitioner2::CfgPath::Edges |
| typedef std::vector<ControlFlowGraph::ConstVertexIterator> Rose::BinaryAnalysis::Partitioner2::CfgPath::Vertices |
|
inline |
|
inlineexplicit |
|
inlineexplicit |
|
inline |
|
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.
|
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().
|
inline |
|
inline |
|
inline |
|
inline |
| 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::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.
1.9.8