cprover
call_graph_helpers.cpp File Reference

Function Call Graph Helpers. More...

Include dependency graph for call_graph_helpers.cpp:

Go to the source code of this file.

Functions

static std::set< irep_idtget_neighbours (const call_grapht::directed_grapht &graph, const irep_idt &function, bool forwards)
 Get either callers or callees of a given function. More...
 
std::set< irep_idtget_callees (const call_grapht::directed_grapht &graph, const irep_idt &function)
 Get functions directly callable from a given function. More...
 
std::set< irep_idtget_callers (const call_grapht::directed_grapht &graph, const irep_idt &function)
 Get functions that call a given function. More...
 
static std::set< irep_idtget_connected_functions (const call_grapht::directed_grapht &graph, const irep_idt &function, bool forwards)
 Get either reachable functions or functions that can reach a given function. More...
 
std::set< irep_idtget_reachable_functions (const call_grapht::directed_grapht &graph, const irep_idt &function)
 Get functions reachable from a given function. More...
 
std::set< irep_idtget_reaching_functions (const call_grapht::directed_grapht &graph, const irep_idt &function)
 Get functions that can reach a given function. More...
 
std::set< irep_idtget_functions_reachable_within_n_steps (const call_grapht::directed_grapht &graph, const std::set< irep_idt > &start_functions, std::size_t n)
 Get either callers or callees reachable from a given list of functions within N steps. More...
 
std::set< irep_idtget_functions_reachable_within_n_steps (const call_grapht::directed_grapht &graph, const irep_idt &start_function, std::size_t n)
 Get either callers or callees reachable from a given list of functions within N steps. More...
 
void disconnect_unreachable_functions (call_grapht::directed_grapht &graph, const irep_idt &function)
 Disconnects all functions in the call graph that are unreachable from a given start function. More...
 
std::list< irep_idtget_shortest_function_path (const call_grapht::directed_grapht &graph, const irep_idt &src, const irep_idt &dest)
 Get list of functions on the shortest path between two functions. More...
 

Detailed Description

Function Call Graph Helpers.

Definition in file call_graph_helpers.cpp.

Function Documentation

◆ disconnect_unreachable_functions()

void disconnect_unreachable_functions ( call_grapht::directed_grapht graph,
const irep_idt function 
)

Disconnects all functions in the call graph that are unreachable from a given start function.

Removing nodes requires re-indexing, so instead we disconnect them, removing all in and out edges from those nodes. This speeds up backwards reachability.

Parameters
graphcall graph
functionstart function

Definition at line 100 of file call_graph_helpers.cpp.

References grapht< N >::disconnect_unreachable(), and call_grapht::directed_grapht::get_node_index().

◆ get_callees()

std::set<irep_idt> get_callees ( const call_grapht::directed_grapht graph,
const irep_idt function 
)

Get functions directly callable from a given function.

Parameters
graphcall graph
functionfunction to query
Returns
set of called functions

Definition at line 31 of file call_graph_helpers.cpp.

References get_neighbours().

◆ get_callers()

std::set<irep_idt> get_callers ( const call_grapht::directed_grapht graph,
const irep_idt function 
)

Get functions that call a given function.

Parameters
graphcall graph
functionfunction to query
Returns
set of caller functions

Definition at line 37 of file call_graph_helpers.cpp.

References get_neighbours().

◆ get_connected_functions()

static std::set<irep_idt> get_connected_functions ( const call_grapht::directed_grapht graph,
const irep_idt function,
bool  forwards 
)
static

Get either reachable functions or functions that can reach a given function.

In both cases the query function itself is included.

Parameters
graphcall graph
functionfunction to query
forwardsif true, get reachable functions; otherwise get functions that can reach the given function.

Definition at line 49 of file call_graph_helpers.cpp.

References call_grapht::directed_grapht::get_node_index(), and grapht< N >::get_reachable().

Referenced by get_reachable_functions(), and get_reaching_functions().

◆ get_functions_reachable_within_n_steps() [1/2]

std::set<irep_idt> get_functions_reachable_within_n_steps ( const call_grapht::directed_grapht graph,
const std::set< irep_idt > &  start_functions,
std::size_t  n 
)

Get either callers or callees reachable from a given list of functions within N steps.

Parameters
graphcall graph
start_functionsset of start functions
nnumber of steps to consider
Returns
set of functions that can be reached from the start function including the start function

Definition at line 74 of file call_graph_helpers.cpp.

References grapht< N >::depth_limited_search(), and call_grapht::directed_grapht::get_node_index().

Referenced by aggressive_slicert::doit(), and get_functions_reachable_within_n_steps().

◆ get_functions_reachable_within_n_steps() [2/2]

std::set<irep_idt> get_functions_reachable_within_n_steps ( const call_grapht::directed_grapht graph,
const irep_idt start_function,
std::size_t  n 
)

Get either callers or callees reachable from a given list of functions within N steps.

Parameters
graphcall graph
start_functionsingle start function
nnumber of steps to consider
Returns
set of functions that can be reached from the start function including the start function

Definition at line 91 of file call_graph_helpers.cpp.

References get_functions_reachable_within_n_steps().

◆ get_neighbours()

static std::set<irep_idt> get_neighbours ( const call_grapht::directed_grapht graph,
const irep_idt function,
bool  forwards 
)
static

Get either callers or callees of a given function.

Parameters
graphcall graph
functionfunction to query
forwardsif true, get callees; otherwise get callers.

Definition at line 18 of file call_graph_helpers.cpp.

References call_grapht::directed_grapht::get_node_index(), and grapht< N >::out().

Referenced by get_callees(), and get_callers().

◆ get_reachable_functions()

std::set<irep_idt> get_reachable_functions ( const call_grapht::directed_grapht graph,
const irep_idt function 
)

Get functions reachable from a given function.

Parameters
graphcall graph
functionfunction to query
Returns
set of reachable functions, including function

Definition at line 62 of file call_graph_helpers.cpp.

References get_connected_functions().

◆ get_reaching_functions()

std::set<irep_idt> get_reaching_functions ( const call_grapht::directed_grapht graph,
const irep_idt function 
)

Get functions that can reach a given function.

Parameters
graphcall graph
functionfunction to query
Returns
set of functions that can reach the target, including function

Definition at line 68 of file call_graph_helpers.cpp.

References get_connected_functions().

Referenced by aggressive_slicert::note_functions_to_keep().

◆ get_shortest_function_path()

std::list<irep_idt> get_shortest_function_path ( const call_grapht::directed_grapht graph,
const irep_idt src,
const irep_idt dest 
)

Get list of functions on the shortest path between two functions.

Parameters
graphcall graph
srcfunction to start from
destfunction to reach
Returns
list of functions on shortest path

Definition at line 107 of file call_graph_helpers.cpp.

References call_grapht::directed_grapht::get_node_index(), and grapht< N >::shortest_path().

Referenced by aggressive_slicert::note_functions_to_keep().