cprover
call_grapht Class Reference

A call graph (https://en.wikipedia.org/wiki/Call_graph) for a GOTO model or GOTO functions collection. More...

#include <call_graph.h>

+ Collaboration diagram for call_grapht:

Classes

class  directed_grapht
 Directed graph representation of this call graph. More...
 
struct  edge_with_callsitest
 Edge of the directed graph representation of this call graph. More...
 
struct  function_nodet
 Node of the directed graph representation of this call graph. More...
 

Public Types

typedef std::unordered_set< irep_idt, irep_id_hashnodest
 Type of the nodes in the call graph. More...
 
typedef std::multimap< irep_idt, irep_idtedgest
 Type of the edges in the call graph. More...
 
typedef std::pair< irep_idt, irep_idtedget
 Type of a call graph edge in edgest More...
 
typedef goto_programt::const_targett locationt
 Type of a callsite stored in member callsites More...
 
typedef std::set< locationtlocationst
 Type of a set of callsites. More...
 
typedef std::map< edget, locationstcallsitest
 Type mapping from call-graph edges onto the set of call instructions that make that call. More...
 

Public Member Functions

 call_grapht (bool collect_callsites=false)
 Create empty call graph. More...
 
 call_grapht (const goto_modelt &, bool collect_callsites=false)
 Create complete call graph. More...
 
 call_grapht (const goto_functionst &, bool collect_callsites=false)
 Create complete call graph. More...
 
void output_dot (std::ostream &out) const
 
void output (std::ostream &out) const
 
void output_xml (std::ostream &out) const
 
void add (const irep_idt &caller, const irep_idt &callee)
 Add edge. More...
 
void add (const irep_idt &caller, const irep_idt &callee, locationt callsite)
 Add edge with optional callsite information. More...
 
call_grapht get_inverted () const
 Returns an inverted copy of this call graph. More...
 
directed_grapht get_directed_graph () const
 Returns a grapht representation of this call graph, suitable for use with generic grapht algorithms. More...
 

Static Public Member Functions

static call_grapht create_from_root_function (const goto_modelt &model, const irep_idt &root, bool collect_callsites)
 
static call_grapht create_from_root_function (const goto_functionst &functions, const irep_idt &root, bool collect_callsites)
 

Public Attributes

edgest edges
 Call graph, including duplicate key-value pairs when there are parallel edges (see grapht documentation). More...
 
nodest nodes
 
callsitest callsites
 Map from call-graph edges to a set of callsites that make the given call. More...
 

Protected Member Functions

void add (const irep_idt &function, const goto_programt &body)
 

Private Member Functions

 call_grapht (const goto_modelt &model, const irep_idt &root, bool collect_callsites)
 Create call graph restricted to functions reachable from root More...
 
 call_grapht (const goto_functionst &functions, const irep_idt &root, bool collect_callsites)
 Create call graph restricted to functions reachable from root More...
 
std::string format_callsites (const edget &edge) const
 Prints callsites responsible for a graph edge as comma-separated location numbers, e.g. More...
 

Private Attributes

bool collect_callsites
 

Detailed Description

A call graph (https://en.wikipedia.org/wiki/Call_graph) for a GOTO model or GOTO functions collection.

The public constructors build a complete call graph, while call_grapht::create_from_root_function can be used to create a partial call graph rooted at a particular function.

The graph is stored as a std::multimap, and this class only provides basic tools to construct and query graphs, but it can be exported to a grapht and thus processed using the full graph algorithms library using the get_directed_graph method. See also call_graph_helpers.h for helper methods that work with such grapht-derived call graphs.

The graph may optionally collect (and export) the callsite associated with each edge; pass the collect_callsites parameter to a constructor if you want this functionality, and query the call_grapht::callsites collection.

Definition at line 38 of file call_graph.h.

Member Typedef Documentation

◆ callsitest

Type mapping from call-graph edges onto the set of call instructions that make that call.

Definition at line 100 of file call_graph.h.

◆ edgest

typedef std::multimap<irep_idt, irep_idt> call_grapht::edgest

Type of the edges in the call graph.

Note parallel edges (e.g. A having two callsites both targeting B) result in multiple graph edges.

Definition at line 87 of file call_graph.h.

◆ edget

typedef std::pair<irep_idt, irep_idt> call_grapht::edget

Type of a call graph edge in edgest

Definition at line 90 of file call_graph.h.

◆ locationst

Type of a set of callsites.

Definition at line 96 of file call_graph.h.

◆ locationt

Type of a callsite stored in member callsites

Definition at line 93 of file call_graph.h.

◆ nodest

typedef std::unordered_set<irep_idt, irep_id_hash> call_grapht::nodest

Type of the nodes in the call graph.

Definition at line 83 of file call_graph.h.

Constructor & Destructor Documentation

◆ call_grapht() [1/5]

call_grapht::call_grapht ( bool  collect_callsites = false)
explicit

Create empty call graph.

Parameters
collect_callsitesif true, then each added graph edge will have the calling instruction recorded in callsites map.

Definition at line 20 of file call_graph.cpp.

◆ call_grapht() [2/5]

call_grapht::call_grapht ( const goto_modelt goto_model,
bool  collect_callsites = false 
)
explicit

Create complete call graph.

Parameters
goto_modelmodel to search for callsites
collect_callsitesif true, then each added graph edge will have the calling instruction recorded in callsites map.

Definition at line 29 of file call_graph.cpp.

◆ call_grapht() [3/5]

call_grapht::call_grapht ( const goto_functionst goto_functions,
bool  collect_callsites = false 
)
explicit

Create complete call graph.

Parameters
goto_functionsfunctions to search for callsites
collect_callsitesif true, then each added graph edge will have the calling instruction recorded in callsites map.

Definition at line 38 of file call_graph.cpp.

◆ call_grapht() [4/5]

call_grapht::call_grapht ( const goto_modelt goto_model,
const irep_idt root,
bool  collect_callsites 
)
private

Create call graph restricted to functions reachable from root

Parameters
goto_modelmodel to search for callsites
rootfunction to start exploring the graph
collect_callsitesif true, then each added graph edge will have the calling instruction recorded in callsites map.

Definition at line 114 of file call_graph.cpp.

◆ call_grapht() [5/5]

call_grapht::call_grapht ( const goto_functionst goto_functions,
const irep_idt root,
bool  collect_callsites 
)
private

Create call graph restricted to functions reachable from root

Parameters
goto_functionsfunctions to search for callsites
rootfunction to start exploring the graph
collect_callsitesif true, then each added graph edge will have the calling instruction recorded in callsites map.

Definition at line 74 of file call_graph.cpp.

Member Function Documentation

◆ add() [1/3]

void call_grapht::add ( const irep_idt caller,
const irep_idt callee 
)

Add edge.

Parameters
callercaller function
calleecallee function

Definition at line 138 of file call_graph.cpp.

◆ add() [2/3]

void call_grapht::add ( const irep_idt caller,
const irep_idt callee,
locationt  callsite 
)

Add edge with optional callsite information.

Parameters
callercaller function
calleecallee function
callsitecall instruction responsible for this edge. Note this is only stored if collect_callsites was specified during construction.

Definition at line 152 of file call_graph.cpp.

◆ add() [3/3]

void call_grapht::add ( const irep_idt function,
const goto_programt body 
)
protected

Definition at line 122 of file call_graph.cpp.

◆ create_from_root_function() [1/2]

static call_grapht call_grapht::create_from_root_function ( const goto_modelt model,
const irep_idt root,
bool  collect_callsites 
)
inlinestatic

Definition at line 48 of file call_graph.h.

◆ create_from_root_function() [2/2]

static call_grapht call_grapht::create_from_root_function ( const goto_functionst functions,
const irep_idt root,
bool  collect_callsites 
)
inlinestatic

Definition at line 56 of file call_graph.h.

◆ format_callsites()

std::string call_grapht::format_callsites ( const edget edge) const
private

Prints callsites responsible for a graph edge as comma-separated location numbers, e.g.

"{1, 2, 3}".

Parameters
edgegraph edge
Returns
pretty representation of edge callsites

Definition at line 240 of file call_graph.cpp.

◆ get_directed_graph()

call_grapht::directed_grapht call_grapht::get_directed_graph ( ) const

Returns a grapht representation of this call graph, suitable for use with generic grapht algorithms.

Note that parallel edges in call_grapht (e.g. A { B(); B(); } appearing as two A->B edges) will be condensed in the grapht output, so only one edge will appear. If collect_callsites was set when this call-graph was constructed the edge will be annotated with the call-site set.

Returns
grapht representation of this call_grapht

Definition at line 208 of file call_graph.cpp.

◆ get_inverted()

call_grapht call_grapht::get_inverted ( ) const

Returns an inverted copy of this call graph.

Returns
Inverted (callee -> caller) call graph

Definition at line 164 of file call_graph.cpp.

◆ output()

void call_grapht::output ( std::ostream &  out) const

Definition at line 271 of file call_graph.cpp.

◆ output_dot()

void call_grapht::output_dot ( std::ostream &  out) const

Definition at line 254 of file call_graph.cpp.

◆ output_xml()

void call_grapht::output_xml ( std::ostream &  out) const

Definition at line 281 of file call_graph.cpp.

Member Data Documentation

◆ callsites

callsitest call_grapht::callsites

Map from call-graph edges to a set of callsites that make the given call.

Definition at line 111 of file call_graph.h.

◆ collect_callsites

bool call_grapht::collect_callsites
private

Definition at line 164 of file call_graph.h.

◆ edges

edgest call_grapht::edges

Call graph, including duplicate key-value pairs when there are parallel edges (see grapht documentation).

This representation is retained for backward compatibility; use get_directed_graph() to get a generic directed graph representation that provides more graph algorithms (shortest path, SCCs and so on).

Definition at line 107 of file call_graph.h.

◆ nodes

nodest call_grapht::nodes

Definition at line 108 of file call_graph.h.


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