ROSE
0.9.10.89

Binary function call analysis.
This class serves mostly to organize the functions that operate on function calls, but also provides a container for various settings that influence the function call analyses, such as vertex and edge filters.
Function call graphs can be computed over any subtree of the AST, although one usually does so over an entire binary interpretation (SgAsmInterpretation). The vertex and edge filters can restrict which functions and call edges are considered by the various methods of this class.
Definition at line 19 of file BinaryFunctionCall.h.
#include <BinaryFunctionCall.h>
Classes  
class  EdgeFilter 
Filter for edges. More...  
class  VertexFilter 
Filter for vertices. More...  
Public Types  
typedef boost::adjacency_list< boost::setS, boost::vecS, boost::bidirectionalS, boost::property< boost::vertex_name_t, SgAsmFunction * > >  Graph 
The default function call graph type. More...  
Public Member Functions  
template<class FunctionCallGraph >  
void  cache_vertex_descriptors (const FunctionCallGraph &) 
Cache vertex descriptors in AST. More...  
void  set_vertex_filter (VertexFilter *filter) 
Manipulate the vertex filter. More...  
VertexFilter *  get_vertex_filter () const 
Manipulate the vertex filter. More...  
void  set_edge_filter (EdgeFilter *filter) 
Manipulate the edge filter. More...  
EdgeFilter *  get_edge_filter () const 
Manipulate the edge filter. More...  
bool  is_vertex_filtered (SgAsmFunction *func, VertexFilter *filter) 
Determines if a vertex is filtered out. More...  
bool  is_vertex_filtered (SgAsmFunction *func) 
Determines if a vertex is filtered out. More...  
bool  is_edge_filtered (SgAsmFunction *src, SgAsmFunction *dst, EdgeFilter *filter) 
Determines if an edge is filtered out. More...  
bool  is_edge_filtered (SgAsmFunction *src, SgAsmFunction *dst) 
Determines if an edge is filtered out. More...  
template<class FunctionCallGraph , class ControlFlowGraph >  
FunctionCallGraph  build_cg_from_cfg (const ControlFlowGraph &) 
Build a function call graph from a control flow graph. More...  
template<class ControlFlowGraph , class FunctionCallGraph >  
void  build_cg_from_cfg (const ControlFlowGraph &cfg, FunctionCallGraph &cg) 
Build a function call graph from a control flow graph. More...  
template<class FunctionCallGraph >  
FunctionCallGraph  build_cg_from_ast (SgNode *root) 
Build a function call graph from an AST. More...  
template<class FunctionCallGraph >  
void  build_cg_from_ast (SgNode *root, FunctionCallGraph &cg) 
Build a function call graph from an AST. More...  
template<class FunctionCallGraph >  
FunctionCallGraph  copy (const FunctionCallGraph &src) 
Copies a graph while filtering. More...  
template<class FunctionCallGraph >  
void  copy (const FunctionCallGraph &src, FunctionCallGraph &dst) 
Copies a graph while filtering. More...  
Protected Attributes  
VertexFilter *  vertex_filter 
EdgeFilter *  edge_filter 
typedef boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, boost::property<boost::vertex_name_t, SgAsmFunction*> > Rose::BinaryAnalysis::FunctionCall::Graph 
The default function call graph type.
A function call graph is simply a Boost graph whose vertex descriptors are integers and whose vertices point to SgAsmFunction nodes in the AST (via the boost::vertex_name property). The graph edges represent function calls from one SgAsmFunction to another. Since this graph is a Boost graph, it is endowed with all the features of a Boost graph and can be the operand of the various Boost graph algorithms. See build_cg() for specifics about what is included in such a graph.
Another way to represent function calls is to adapt a global control flow graph (Rose::BinaryAnalysis::ControlFlowGraph) to include only the edges (and their incident vertices) that flow from one function to another. The advantage of using a control flow graph to represent function call information is that each call site will be included in the function call graph due to the fact that the control flow graph vertices are blocks (SgAsmBlock) rather than functions (SgAsmFunction).
It is common to need a type for the vertices and edges. Boost graphs store this information in graph_traits and users should use that to obtain those types. Doing so will, in the long run, make your code more extensible since the only datatype you're depending on is the graph itself–change the graph type and the vertex and edge types will automatically adjust. See Boost Graph Library documentation for all the available types. The most common are:
Definition at line 54 of file BinaryFunctionCall.h.

inline 
Manipulate the vertex filter.
When building a function call graph, the vertex filter is invoked on each function which is about to be added as a vertex. If the filter returns false then that function is not added to the graph. A null filter accepts all vertices.
Definition at line 89 of file BinaryFunctionCall.h.

inline 
Manipulate the vertex filter.
When building a function call graph, the vertex filter is invoked on each function which is about to be added as a vertex. If the filter returns false then that function is not added to the graph. A null filter accepts all vertices.
Definition at line 90 of file BinaryFunctionCall.h.

inline 
Manipulate the edge filter.
When building a function call graph, the edge filter is invoked for each edge which is about to be added to the graph. If the filter returns false then that edge is not added to the graph. A null filter accepts all edges.
Definition at line 99 of file BinaryFunctionCall.h.

inline 
Manipulate the edge filter.
When building a function call graph, the edge filter is invoked for each edge which is about to be added to the graph. If the filter returns false then that edge is not added to the graph. A null filter accepts all edges.
Definition at line 100 of file BinaryFunctionCall.h.

inline 
Determines if a vertex is filtered out.
Returns true if the vertex would be filtered out by being rejected by the current vertex filter.
Definition at line 108 of file BinaryFunctionCall.h.
Referenced by build_cg_from_ast(), build_cg_from_cfg(), cache_vertex_descriptors(), copy(), and is_vertex_filtered().

inline 
Determines if a vertex is filtered out.
Returns true if the vertex would be filtered out by being rejected by the current vertex filter.
Definition at line 111 of file BinaryFunctionCall.h.
References is_vertex_filtered().

inline 
Determines if an edge is filtered out.
Returns true if the edge would be filtered out by being rejected by the current edge filter.
Definition at line 121 of file BinaryFunctionCall.h.
Referenced by build_cg_from_ast(), build_cg_from_cfg(), copy(), and is_edge_filtered().

inline 
Determines if an edge is filtered out.
Returns true if the edge would be filtered out by being rejected by the current edge filter.
Definition at line 124 of file BinaryFunctionCall.h.
References is_edge_filtered().
void Rose::BinaryAnalysis::FunctionCall::cache_vertex_descriptors  (  const FunctionCallGraph &  cg  ) 
Cache vertex descriptors in AST.
The vertices of a function call graph are of type Vertex, and point at the functions (SgAsmFunction) of the AST. Although most graph algorithms will only need to map Vertex to SgAsmFunction, the inverse mapping is also sometimes useful. That mapping can be stored into an std::map via graph traversal, or stored in the AST itself attached to each SgAsmFunction. Using an std::map requires an O(log N) lookup each time we need to get the vertex descriptor for a function, while storing the vertex descriptor in the AST requires O(1) lookup time.
The vertex descriptors are available via SgAsmFunction::get_cached_vertex(). Other graph types (e.g., dominance graphs) might also use the same cache line. The cached vertex is stored as a size_t, which is the same underlying type for function call graph vertices.
The current vertex filter determines which function nodes are modified.
Definition at line 236 of file BinaryFunctionCall.h.
References Rose::BinaryAnalysis::get_ast_node(), and is_vertex_filtered().
FunctionCallGraph Rose::BinaryAnalysis::FunctionCall::build_cg_from_cfg  (  const ControlFlowGraph &  cfg  ) 
Build a function call graph from a control flow graph.
Given a control flow graph (CFG) spanning multiple functions, create a function call graph (CG) by collapsing vertices in the CFG that belong to a common function. Any resulting selfloop edges will be removed unless the target of the corresponding edge in the CFG was the function entry block (i.e., intrafunction CFG edges whose target is the function's entry block are assumed to be recursive calls, while all other intrafunction CFG edges are omitted from the CG).
The current vertex and edge filters are used to restrict which functions and calls make it into the graph.
Definition at line 293 of file BinaryFunctionCall.h.
void Rose::BinaryAnalysis::FunctionCall::build_cg_from_cfg  (  const ControlFlowGraph &  cfg, 
FunctionCallGraph &  cg  
) 
Build a function call graph from a control flow graph.
Given a control flow graph (CFG) spanning multiple functions, create a function call graph (CG) by collapsing vertices in the CFG that belong to a common function. Any resulting selfloop edges will be removed unless the target of the corresponding edge in the CFG was the function entry block (i.e., intrafunction CFG edges whose target is the function's entry block are assumed to be recursive calls, while all other intrafunction CFG edges are omitted from the CG).
The current vertex and edge filters are used to restrict which functions and calls make it into the graph.
Definition at line 248 of file BinaryFunctionCall.h.
References Rose::BinaryAnalysis::get_ast_node(), SgAsmBlock::get_enclosing_function(), SgAsmFunction::get_entry_block(), is_edge_filtered(), is_vertex_filtered(), and Rose::BinaryAnalysis::put_ast_node().
FunctionCallGraph Rose::BinaryAnalysis::FunctionCall::build_cg_from_ast  (  SgNode *  root  ) 
Build a function call graph from an AST.
Given an AST, traverse the AST beginning at root
and build a function call graph (CG). The function call graph will contain only SgAsmFunction vertices that are in the specified subtree and which are not filtered out by the current vertex filter. Edges also must pass the edge filter to be included in the graph.
The following two methods of constructing a CG should result in identical graphs (although vertex and edge order may be different):
In general, building the function call graph directly from the AST will be faster than first building the control flow graph.
Definition at line 373 of file BinaryFunctionCall.h.
void Rose::BinaryAnalysis::FunctionCall::build_cg_from_ast  (  SgNode *  root, 
FunctionCallGraph &  cg  
) 
Build a function call graph from an AST.
Given an AST, traverse the AST beginning at root
and build a function call graph (CG). The function call graph will contain only SgAsmFunction vertices that are in the specified subtree and which are not filtered out by the current vertex filter. Edges also must pass the edge filter to be included in the graph.
The following two methods of constructing a CG should result in identical graphs (although vertex and edge order may be different):
In general, building the function call graph directly from the AST will be faster than first building the control flow graph.
Definition at line 302 of file BinaryFunctionCall.h.
References SgAsmStatement::get_address(), Rose::BinaryAnalysis::get_ast_node(), SgAsmBlock::get_enclosing_function(), SgAsmBlock::get_successors(), is_edge_filtered(), is_vertex_filtered(), and Rose::BinaryAnalysis::put_ast_node().
FunctionCallGraph Rose::BinaryAnalysis::FunctionCall::copy  (  const FunctionCallGraph &  src  ) 
Copies a graph while filtering.
Copies a graph while applying the current source and destination vertex and edge filters. If all vertices are selected by the vertex filter, then the desintation graph's vertex descriptors will correspond to the same vertices in the source graph (i.e., vertex V in the source will be the same basic block as vertex V in the destination).
If an edge is unfiltered but one of its vertices is filtered, then the edge will not be included in the result.
Definition at line 412 of file BinaryFunctionCall.h.
void Rose::BinaryAnalysis::FunctionCall::copy  (  const FunctionCallGraph &  src, 
FunctionCallGraph &  dst  
) 
Copies a graph while filtering.
Copies a graph while applying the current source and destination vertex and edge filters. If all vertices are selected by the vertex filter, then the desintation graph's vertex descriptors will correspond to the same vertices in the source graph (i.e., vertex V in the source will be the same basic block as vertex V in the destination).
If an edge is unfiltered but one of its vertices is filtered, then the edge will not be included in the result.
Definition at line 382 of file BinaryFunctionCall.h.
References Rose::BinaryAnalysis::get_ast_node(), is_edge_filtered(), is_vertex_filtered(), and Rose::BinaryAnalysis::put_ast_node().