CBMC
call_graph.cpp
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 #include "call_graph.h"
13 
14 #include <util/xml.h>
15 
17 
21 call_grapht::call_grapht(bool collect_callsites):
22  collect_callsites(collect_callsites)
23 {
24 }
25 
30 call_grapht::call_grapht(const goto_modelt &goto_model, bool collect_callsites):
31  call_grapht(goto_model.goto_functions, collect_callsites)
32 {
33 }
34 
40  const goto_functionst &goto_functions, bool collect_callsites):
41  collect_callsites(collect_callsites)
42 {
43  for(const auto &gf_entry : goto_functions.function_map)
44  {
45  const irep_idt &function_name = gf_entry.first;
46  const goto_programt &body = gf_entry.second.body;
47  nodes.insert(function_name);
48  add(function_name, body);
49  }
50 }
51 
52 static void forall_callsites(
53  const goto_programt &body,
54  std::function<void(goto_programt::const_targett, const irep_idt &)> call_task)
55 {
57  {
58  if(i_it->is_function_call())
59  {
60  const exprt &function_expr = i_it->call_function();
62  function_expr.id() == ID_symbol,
63  "call graph computation requires function pointer removal");
64  const irep_idt &callee = to_symbol_expr(function_expr).get_identifier();
65  call_task(i_it, callee);
66  }
67  }
68 }
69 
76  const goto_functionst &goto_functions,
77  const irep_idt &root,
78  bool collect_callsites):
79  collect_callsites(collect_callsites)
80 {
81  std::stack<irep_idt, std::vector<irep_idt>> pending_stack;
82  pending_stack.push(root);
83 
84  while(!pending_stack.empty())
85  {
86  irep_idt function=pending_stack.top();
87  pending_stack.pop();
88 
89  nodes.insert(function);
90 
91  // if function is not in function_map, assume function has no body
92  const auto &it = goto_functions.function_map.find(function);
93  if(it == goto_functions.function_map.end())
94  continue;
95 
96  const goto_programt &goto_program = it->second.body;
97 
99  goto_program,
100  [&](goto_programt::const_targett i_it, const irep_idt &callee)
101  {
102  add(function, callee, i_it);
103  if(edges.find(callee)==edges.end())
104  pending_stack.push(callee);
105  }
106  ); // NOLINT
107  }
108 }
109 
116  const goto_modelt &goto_model,
117  const irep_idt &root,
118  bool collect_callsites):
119  call_grapht(goto_model.goto_functions, root, collect_callsites)
120 {
121 }
122 
124  const irep_idt &function,
125  const goto_programt &body)
126 {
128  body,
129  [&](goto_programt::const_targett i_it, const irep_idt &callee)
130  {
131  add(function, callee, i_it);
132  }
133  ); // NOLINT
134 }
135 
140  const irep_idt &caller,
141  const irep_idt &callee)
142 {
143  edges.insert({caller, callee});
144  nodes.insert(caller);
145  nodes.insert(callee);
146 }
147 
154  const irep_idt &caller,
155  const irep_idt &callee,
156  locationt callsite)
157 {
158  add(caller, callee);
160  callsites[{caller, callee}].insert(callsite);
161 }
162 
166 {
167  call_grapht result;
168  result.nodes = nodes;
169  for(const auto &caller_callee : edges)
170  result.add(caller_callee.second, caller_callee.first);
171  return result;
172 }
173 
177 {
180 
181 public:
182  std::unordered_map<irep_idt, node_indext> function_indices;
183 
185  graph(graph)
186  {
187  }
188 
189  node_indext operator[](const irep_idt &function)
190  {
191  auto findit=function_indices.insert({function, 0});
192  if(findit.second)
193  {
194  node_indext new_index=graph.add_node();
195  findit.first->second=new_index;
196  graph[new_index].function=function;
197  }
198  return findit.first->second;
199  }
200 };
201 
210 {
212  function_indicest function_indices(ret);
213 
214  // To make sure we include unreachable functions we first create indices
215  // for all nodes in the graph
216  for(const irep_idt &function_name : nodes)
217  function_indices[function_name];
218 
219  for(const auto &edge : edges)
220  {
221  auto a_index=function_indices[edge.first];
222  auto b_index=function_indices[edge.second];
223  // Check then create the edge like this to avoid copying the callsites
224  // set once per parallel edge, which could be costly if there are many.
225  if(!ret.has_edge(a_index, b_index))
226  {
227  ret.add_edge(a_index, b_index);
229  ret[a_index].out[b_index].callsites=callsites.at(edge);
230  }
231  }
232 
233  ret.nodes_by_name=std::move(function_indices.function_indices);
234  return ret;
235 }
236 
241 std::string call_grapht::format_callsites(const edget &edge) const
242 {
244  std::string ret="{";
245  for(const locationt &loc : callsites.at(edge))
246  {
247  if(ret.size()>1)
248  ret+=", ";
249  ret+=std::to_string(loc->location_number);
250  }
251  ret+='}';
252  return ret;
253 }
254 
255 void call_grapht::output_dot(std::ostream &out) const
256 {
257  out << "digraph call_graph {\n";
258 
259  for(const auto &edge : edges)
260  {
261  out << " \"" << edge.first << "\" -> "
262  << "\"" << edge.second << "\" "
263  << " [arrowhead=\"vee\"";
265  out << " label=\"" << format_callsites(edge) << "\"";
266  out << "];\n";
267  }
268 
269  out << "}\n";
270 }
271 
272 void call_grapht::output(std::ostream &out) const
273 {
274  for(const auto &edge : edges)
275  {
276  out << edge.first << " -> " << edge.second << "\n";
278  out << " (callsites: " << format_callsites(edge) << ")\n";
279  }
280 }
281 
282 void call_grapht::output_xml(std::ostream &out) const
283 {
284  // Note I don't implement callsite output here; I'll leave that
285  // to the first interested XML user.
287  out << "<!-- XML call-graph representation does not document callsites yet."
288  " If you need this, edit call_grapht::output_xml -->\n";
289  for(const auto &edge : edges)
290  {
291  out << "<call_graph_edge caller=\"";
292  xmlt::escape_attribute(id2string(edge.first), out);
293  out << "\" callee=\"";
294  xmlt::escape_attribute(id2string(edge.second), out);
295  out << "\">\n";
296  }
297 }
298 
299 std::optional<std::size_t>
301 {
302  auto findit=nodes_by_name.find(function);
303  if(findit==nodes_by_name.end())
304  return std::optional<node_indext>();
305  else
306  return findit->second;
307 }
static void forall_callsites(const goto_programt &body, std::function< void(goto_programt::const_targett, const irep_idt &)> call_task)
Definition: call_graph.cpp:52
Function Call Graphs.
Directed graph representation of this call graph.
Definition: call_graph.h:140
std::optional< node_indext > get_node_index(const irep_idt &function) const
Find the graph node by function name.
Definition: call_graph.cpp:300
std::unordered_map< irep_idt, node_indext > nodes_by_name
Maps function names onto node indices.
Definition: call_graph.h:144
A call graph (https://en.wikipedia.org/wiki/Call_graph) for a GOTO model or GOTO functions collection...
Definition: call_graph.h:44
void add(const irep_idt &caller, const irep_idt &callee)
Add edge.
Definition: call_graph.cpp:139
bool collect_callsites
Definition: call_graph.h:169
nodest nodes
Definition: call_graph.h:113
std::pair< irep_idt, irep_idt > edget
Type of a call graph edge in edgest
Definition: call_graph.h:95
edgest edges
Call graph, including duplicate key-value pairs when there are parallel edges (see grapht documentati...
Definition: call_graph.h:112
call_grapht get_inverted() const
Returns an inverted copy of this call graph.
Definition: call_graph.cpp:165
void output_dot(std::ostream &out) const
Definition: call_graph.cpp:255
std::string format_callsites(const edget &edge) const
Prints callsites responsible for a graph edge as comma-separated location numbers,...
Definition: call_graph.cpp:241
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:209
call_grapht(bool collect_callsites=false)
Create empty call graph.
Definition: call_graph.cpp:21
void output(std::ostream &out) const
Definition: call_graph.cpp:272
callsitest callsites
Map from call-graph edges to a set of callsites that make the given call.
Definition: call_graph.h:116
void output_xml(std::ostream &out) const
Definition: call_graph.cpp:282
goto_programt::const_targett locationt
Type of a callsite stored in member callsites
Definition: call_graph.h:98
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:38
Base class for all expressions.
Definition: expr.h:56
Helper class that maintains a map from function name to grapht node index and adds nodes to the graph...
Definition: call_graph.cpp:177
std::unordered_map< irep_idt, node_indext > function_indices
Definition: call_graph.cpp:182
call_grapht::directed_grapht::node_indext node_indext
Definition: call_graph.cpp:178
call_grapht::directed_grapht & graph
Definition: call_graph.cpp:179
node_indext operator[](const irep_idt &function)
Definition: call_graph.cpp:189
function_indicest(call_grapht::directed_grapht &graph)
Definition: call_graph.cpp:184
A collection of goto functions.
function_mapt function_map
A generic container class for the GOTO intermediate representation of one function.
Definition: goto_program.h:73
instructionst::const_iterator const_targett
Definition: goto_program.h:615
nodet::node_indext node_indext
Definition: graph.h:173
bool has_edge(node_indext i, node_indext j) const
Definition: graph.h:192
node_indext add_node(arguments &&... values)
Definition: graph.h:180
void add_edge(node_indext a, node_indext b)
Definition: graph.h:232
const edgest & out(node_indext n) const
Definition: graph.h:227
const irep_idt & id() const
Definition: irep.h:384
const irep_idt & get_identifier() const
Definition: std_expr.h:160
static void escape_attribute(const std::string &s, std::ostream &out)
escaping for XML attributes, assuming that double quotes " are used consistently, not single quotes
Definition: xml.cpp:121
Symbol Table + CFG.
#define forall_goto_program_instructions(it, program)
const std::string & id2string(const irep_idt &d)
Definition: irep.h:40
#define PRECONDITION_WITH_DIAGNOSTICS(CONDITION,...)
Definition: invariant.h:464
#define PRECONDITION(CONDITION)
Definition: invariant.h:463
const symbol_exprt & to_symbol_expr(const exprt &expr)
Cast an exprt to a symbol_exprt.
Definition: std_expr.h:272
std::string to_string(const string_not_contains_constraintt &expr)
Used for debug printing.