ROSE
0.9.12.28

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 interedge 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 <CfgPath.h>
Public Types  
typedef std::vector< ControlFlowGraph::ConstEdgeIterator >  Edges 
Stack of interconnected edges. More...  
typedef std::vector< ControlFlowGraph::ConstVertexIterator >  Vertices 
Stack of vertices. More...  
typedef Sawyer::Attribute::Storage< Sawyer::SingleThreadedTag >  Attributes 
Stores userdefined 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 Edges &  edges () 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...  
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...  
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...  
Attributes &  vertexAttributes (size_t) 
Userdefined attributes for the nth vertex. More...  
const Attributes &  vertexAttributes (size_t) const 
Userdefined attributes for the nth vertex. More...  
Attributes &  edgeAttributes (size_t) 
Userdefined attributes for the nth edge. More...  
const Attributes &  edgeAttributes (size_t) const 
Userdefined attributes for the nth edge. More...  
std::vector< ControlFlowGraph::ConstEdgeIterator >  truncate (const ControlFlowGraph::ConstEdgeIterator &) 
Truncate the path. More...  
std::vector< ControlFlowGraph::ConstEdgeIterator >  truncate (const CfgConstEdgeSet &) 
Truncate the path. More...  
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 62 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 75 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 nonempty, 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 nonempty, 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  ) 
Userdefined 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 
Userdefined 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  ) 
Userdefined 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 
Userdefined 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 Function::Ptr &  function = Function::Ptr()  )  const 
Number of function calls.
Counts the number of E_FUNCTION_CALL edges in a path. If a nonnull 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 nonnull 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 nonnull 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 nonnull 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 userdefined 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.