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 
22 {
23 public:
24  explicit call_grapht(bool collect_callsites=false);
25  explicit call_grapht(const goto_modelt &, bool collect_callsites=false);
26  explicit call_grapht(const goto_functionst &, bool collect_callsites=false);
27 
28  // These two functions build a call graph restricted to functions
29  // reachable from the given root.
30 
32  const goto_modelt &model,
33  const irep_idt &root,
34  bool collect_callsites)
35  {
36  return call_grapht(model, root, collect_callsites);
37  }
38 
40  const goto_functionst &functions,
41  const irep_idt &root,
42  bool collect_callsites)
43  {
44  return call_grapht(functions, root, collect_callsites);
45  }
46 
47  // Constructors used to implement the above:
48 
49 private:
51  const goto_modelt &model,
52  const irep_idt &root,
53  bool collect_callsites);
55  const goto_functionst &functions,
56  const irep_idt &root,
57  bool collect_callsites);
58 
59 public:
60 
61  void output_dot(std::ostream &out) const;
62  void output(std::ostream &out) const;
63  void output_xml(std::ostream &out) const;
64 
66  typedef std::unordered_set<irep_idt, irep_id_hash> nodest;
67 
70  typedef std::multimap<irep_idt, irep_idt> edgest;
71 
73  typedef std::pair<irep_idt, irep_idt> edget;
74 
77 
79  typedef std::set<locationt> locationst;
80 
83  typedef std::map<edget, locationst> callsitest;
84 
92 
95 
96  void add(const irep_idt &caller, const irep_idt &callee);
97  void add(const irep_idt &caller, const irep_idt &callee, locationt callsite);
98 
99  call_grapht get_inverted() const;
100 
103  {
107  };
108 
110  struct function_nodet : public graph_nodet<edge_with_callsitest>
111  {
113  irep_idt function;
114  };
115 
117  class directed_grapht : public ::grapht<function_nodet>
118  {
119  friend class call_grapht;
120 
122  std::unordered_map<irep_idt, node_indext> nodes_by_name;
123 
124  public:
128  optionalt<node_indext> get_node_index(const irep_idt &function) const;
129 
131  typedef std::unordered_map<irep_idt, node_indext> nodes_by_namet;
132 
136  {
137  return nodes_by_name;
138  }
139  };
140 
141  directed_grapht get_directed_graph() const;
142 
143 protected:
144  void add(const irep_idt &function,
145  const goto_programt &body);
146 private:
148  std::string format_callsites(const edget &edge) const;
149 };
150 
151 #endif // CPROVER_ANALYSES_CALL_GRAPH_H
call_grapht(bool collect_callsites=false)
Create empty call graph.
Definition: call_graph.cpp:20
void add(const irep_idt &caller, const irep_idt &callee)
Add edge.
Definition: call_graph.cpp:133
A generic directed graph with a parametric node type.
Definition: graph.h:133
goto_programt::const_targett locationt
Type of a callsite stored in member callsites
Definition: call_graph.h:76
Edge of the directed graph representation of this call graph.
Definition: call_graph.h:102
locationst callsites
Callsites responsible for this graph edge.
Definition: call_graph.h:106
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:83
bool collect_callsites
Definition: call_graph.h:147
optionalt< node_indext > get_node_index(const irep_idt &function) const
Find the graph node by function name.
Definition: call_graph.cpp:293
Node of the directed graph representation of this call graph.
Definition: call_graph.h:110
std::unordered_map< irep_idt, node_indext > nodes_by_namet
Type of the node name -> node index map.
Definition: call_graph.h:131
Symbol Table + CFG.
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:203
std::string format_callsites(const edget &edge) const
Prints callsites responsible for a graph edge as comma-separated location numbers, e.g.
Definition: call_graph.cpp:235
void output_xml(std::ostream &out) const
Definition: call_graph.cpp:276
nonstd::optional< T > optionalt
Definition: optional.h:35
void output_dot(std::ostream &out) const
Definition: call_graph.cpp:249
instructionst::const_iterator const_targett
Definition: goto_program.h:398
std::unordered_map< irep_idt, node_indext > nodes_by_name
Maps function names onto node indices.
Definition: call_graph.h:122
callsitest callsites
Map from call-graph edges to a set of callsites that make the given call.
Definition: call_graph.h:94
static call_grapht create_from_root_function(const goto_modelt &model, const irep_idt &root, bool collect_callsites)
Definition: call_graph.h:31
void output(std::ostream &out) const
Definition: call_graph.cpp:266
std::unordered_set< irep_idt, irep_id_hash > nodest
Type of the nodes in the call graph.
Definition: call_graph.h:66
A generic container class for the GOTO intermediate representation of one function.
Definition: goto_program.h:70
std::set< locationt > locationst
Type of a set of callsites.
Definition: call_graph.h:79
A Template Class for Graphs.
static call_grapht create_from_root_function(const goto_functionst &functions, const irep_idt &root, bool collect_callsites)
Definition: call_graph.h:39
nodest nodes
Definition: call_graph.h:91
edgest edges
Call graph, including duplicate key-value pairs when there are parallel edges (see grapht documentati...
Definition: call_graph.h:90
Directed graph representation of this call graph.
Definition: call_graph.h:117
const nodes_by_namet & get_nodes_by_name() const
Get the node name -> node index map.
Definition: call_graph.h:135
std::multimap< irep_idt, irep_idt > edgest
Type of the edges in the call graph.
Definition: call_graph.h:70
std::pair< irep_idt, irep_idt > edget
Type of a call graph edge in edgest
Definition: call_graph.h:73
call_grapht get_inverted() const
Returns an inverted copy of this call graph.
Definition: call_graph.cpp:159
This class represents a node in a directed graph.
Definition: graph.h:34