cprover
call_graph.h
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Function Call Graphs
4 
5 Author: Daniel Kroening, kroening@kroening.com
6 
7 \*******************************************************************/
8 
11 
12 #ifndef CPROVER_ANALYSES_CALL_GRAPH_H
13 #define CPROVER_ANALYSES_CALL_GRAPH_H
14 
15 #include <iosfwd>
16 #include <map>
17 
19 #include <util/graph.h>
20 
39 {
40 public:
41  explicit call_grapht(bool collect_callsites=false);
42  explicit call_grapht(const goto_modelt &, bool collect_callsites=false);
43  explicit call_grapht(const goto_functionst &, bool collect_callsites=false);
44 
45  // These two functions build a call graph restricted to functions
46  // reachable from the given root.
47 
49  const goto_modelt &model,
50  const irep_idt &root,
51  bool collect_callsites)
52  {
53  return call_grapht(model, root, collect_callsites);
54  }
55 
57  const goto_functionst &functions,
58  const irep_idt &root,
59  bool collect_callsites)
60  {
61  return call_grapht(functions, root, collect_callsites);
62  }
63 
64  // Constructors used to implement the above:
65 
66 private:
68  const goto_modelt &model,
69  const irep_idt &root,
70  bool collect_callsites);
72  const goto_functionst &functions,
73  const irep_idt &root,
74  bool collect_callsites);
75 
76 public:
77 
78  void output_dot(std::ostream &out) const;
79  void output(std::ostream &out) const;
80  void output_xml(std::ostream &out) const;
81 
83  typedef std::unordered_set<irep_idt, irep_id_hash> nodest;
84 
87  typedef std::multimap<irep_idt, irep_idt> edgest;
88 
90  typedef std::pair<irep_idt, irep_idt> edget;
91 
94 
96  typedef std::set<locationt> locationst;
97 
100  typedef std::map<edget, locationst> callsitest;
101 
109 
112 
113  void add(const irep_idt &caller, const irep_idt &callee);
114  void add(const irep_idt &caller, const irep_idt &callee, locationt callsite);
115 
116  call_grapht get_inverted() const;
117 
120  {
124  };
125 
127  struct function_nodet : public graph_nodet<edge_with_callsitest>
128  {
130  irep_idt function;
131  };
132 
134  class directed_grapht : public ::grapht<function_nodet>
135  {
136  friend class call_grapht;
137 
139  std::unordered_map<irep_idt, node_indext> nodes_by_name;
140 
141  public:
145  optionalt<node_indext> get_node_index(const irep_idt &function) const;
146 
148  typedef std::unordered_map<irep_idt, node_indext> nodes_by_namet;
149 
153  {
154  return nodes_by_name;
155  }
156  };
157 
158  directed_grapht get_directed_graph() const;
159 
160 protected:
161  void add(const irep_idt &function,
162  const goto_programt &body);
163 private:
165  std::string format_callsites(const edget &edge) const;
166 };
167 
168 #endif // CPROVER_ANALYSES_CALL_GRAPH_H
dstringt
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:37
call_grapht::edgest
std::multimap< irep_idt, irep_idt > edgest
Type of the edges in the call graph.
Definition: call_graph.h:87
call_grapht::collect_callsites
bool collect_callsites
Definition: call_graph.h:164
call_grapht::directed_grapht::get_nodes_by_name
const nodes_by_namet & get_nodes_by_name() const
Get the node name -> node index map.
Definition: call_graph.h:152
call_grapht::callsitest
std::map< edget, locationst > callsitest
Type mapping from call-graph edges onto the set of call instructions that make that call.
Definition: call_graph.h:100
call_grapht::get_inverted
call_grapht get_inverted() const
Returns an inverted copy of this call graph.
Definition: call_graph.cpp:164
call_grapht::directed_grapht::get_node_index
optionalt< node_indext > get_node_index(const irep_idt &function) const
Find the graph node by function name.
Definition: call_graph.cpp:298
call_grapht::call_grapht
call_grapht(bool collect_callsites=false)
Create empty call graph.
Definition: call_graph.cpp:20
grapht
A generic directed graph with a parametric node type.
Definition: graph.h:168
call_grapht::edge_with_callsitest::callsites
locationst callsites
Callsites responsible for this graph edge.
Definition: call_graph.h:123
goto_model.h
Symbol Table + CFG.
goto_modelt
Definition: goto_model.h:26
call_grapht::output_xml
void output_xml(std::ostream &out) const
Definition: call_graph.cpp:281
call_grapht::output_dot
void output_dot(std::ostream &out) const
Definition: call_graph.cpp:254
call_grapht::create_from_root_function
static call_grapht create_from_root_function(const goto_modelt &model, const irep_idt &root, bool collect_callsites)
Definition: call_graph.h:48
call_grapht::nodest
std::unordered_set< irep_idt, irep_id_hash > nodest
Type of the nodes in the call graph.
Definition: call_graph.h:83
call_grapht::create_from_root_function
static call_grapht create_from_root_function(const goto_functionst &functions, const irep_idt &root, bool collect_callsites)
Definition: call_graph.h:56
call_grapht::directed_grapht
Directed graph representation of this call graph.
Definition: call_graph.h:135
call_grapht::directed_grapht::nodes_by_name
std::unordered_map< irep_idt, node_indext > nodes_by_name
Maps function names onto node indices.
Definition: call_graph.h:139
call_grapht::get_directed_graph
directed_grapht get_directed_graph() const
Returns a grapht representation of this call graph, suitable for use with generic grapht algorithms.
Definition: call_graph.cpp:208
optionalt
nonstd::optional< T > optionalt
Definition: optional.h:35
call_grapht::format_callsites
std::string format_callsites(const edget &edge) const
Prints callsites responsible for a graph edge as comma-separated location numbers,...
Definition: call_graph.cpp:240
goto_functionst
A collection of goto functions.
Definition: goto_functions.h:23
call_grapht
A call graph (https://en.wikipedia.org/wiki/Call_graph) for a GOTO model or GOTO functions collection...
Definition: call_graph.h:39
call_grapht::function_nodet
Node of the directed graph representation of this call graph.
Definition: call_graph.h:128
call_grapht::edget
std::pair< irep_idt, irep_idt > edget
Type of a call graph edge in edgest
Definition: call_graph.h:90
graph.h
A Template Class for Graphs.
call_grapht::callsites
callsitest callsites
Map from call-graph edges to a set of callsites that make the given call.
Definition: call_graph.h:111
graph_nodet
This class represents a node in a directed graph.
Definition: graph.h:36
call_grapht::output
void output(std::ostream &out) const
Definition: call_graph.cpp:271
call_grapht::directed_grapht::nodes_by_namet
std::unordered_map< irep_idt, node_indext > nodes_by_namet
Type of the node name -> node index map.
Definition: call_graph.h:148
goto_programt
A generic container class for the GOTO intermediate representation of one function.
Definition: goto_program.h:73
goto_programt::const_targett
instructionst::const_iterator const_targett
Definition: goto_program.h:580
call_grapht::locationst
std::set< locationt > locationst
Type of a set of callsites.
Definition: call_graph.h:96
call_grapht::add
void add(const irep_idt &caller, const irep_idt &callee)
Add edge.
Definition: call_graph.cpp:138
call_grapht::locationt
goto_programt::const_targett locationt
Type of a callsite stored in member callsites
Definition: call_graph.h:93
call_grapht::nodes
nodest nodes
Definition: call_graph.h:108
call_grapht::edge_with_callsitest
Edge of the directed graph representation of this call graph.
Definition: call_graph.h:120
call_grapht::edges
edgest edges
Call graph, including duplicate key-value pairs when there are parallel edges (see grapht documentati...
Definition: call_graph.h:107