ROSE  0.9.9.168
Classes | Public Types | Public Member Functions | Protected Attributes | List of all members
Rose::BinaryAnalysis::FunctionCall Class Reference

Description

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>

Collaboration diagram for Rose::BinaryAnalysis::FunctionCall:
Collaboration graph
[legend]

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...
 
VertexFilterget_vertex_filter () const
 Manipulate the vertex filter. More...
 
void set_edge_filter (EdgeFilter *filter)
 Manipulate the edge filter. More...
 
EdgeFilterget_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

VertexFiltervertex_filter
 
EdgeFilteredge_filter
 

Member Typedef Documentation

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:

typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef boost::graph_traits<Graph>::edge_descriptor Edge;

Definition at line 54 of file BinaryFunctionCall.h.

Member Function Documentation

void Rose::BinaryAnalysis::FunctionCall::set_vertex_filter ( VertexFilter filter)
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.

VertexFilter* Rose::BinaryAnalysis::FunctionCall::get_vertex_filter ( ) const
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.

void Rose::BinaryAnalysis::FunctionCall::set_edge_filter ( EdgeFilter filter)
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.

EdgeFilter* Rose::BinaryAnalysis::FunctionCall::get_edge_filter ( ) const
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.

bool Rose::BinaryAnalysis::FunctionCall::is_vertex_filtered ( SgAsmFunction func,
VertexFilter filter 
)
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().

bool Rose::BinaryAnalysis::FunctionCall::is_vertex_filtered ( SgAsmFunction func)
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().

bool Rose::BinaryAnalysis::FunctionCall::is_edge_filtered ( SgAsmFunction src,
SgAsmFunction dst,
EdgeFilter filter 
)
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().

bool Rose::BinaryAnalysis::FunctionCall::is_edge_filtered ( SgAsmFunction src,
SgAsmFunction dst 
)
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().

template<class FunctionCallGraph >
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().

template<class FunctionCallGraph , class ControlFlowGraph >
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 self-loop edges will be removed unless the target of the corresponding edge in the CFG was the function entry block (i.e., intra-function CFG edges whose target is the function's entry block are assumed to be recursive calls, while all other intra-function 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.

template<class ControlFlowGraph , class FunctionCallGraph >
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 self-loop edges will be removed unless the target of the corresponding edge in the CFG was the function entry block (i.e., intra-function CFG edges whose target is the function's entry block are assumed to be recursive calls, while all other intra-function 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().

template<class FunctionCallGraph >
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):

using namespace Rose::BinaryAnalysis;
typedef ControlFlow::Graph CFG;
SgAsmNode *node = ...;
// Method 1
// Method 2
CFG cfg = ControlFlow().build_block_cfg_from_ast<CFG>(node);
CG cg2 = FunctionCall().build_cg_from_cfg<CG>(cfg);

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.

template<class FunctionCallGraph >
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):

using namespace Rose::BinaryAnalysis;
typedef ControlFlow::Graph CFG;
SgAsmNode *node = ...;
// Method 1
// Method 2
CFG cfg = ControlFlow().build_block_cfg_from_ast<CFG>(node);
CG cg2 = FunctionCall().build_cg_from_cfg<CG>(cfg);

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().

template<class FunctionCallGraph >
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.

template<class FunctionCallGraph >
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().


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