cprover
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/std_expr.h>
15 #include <util/xml.h>
16 
20 call_grapht::call_grapht(bool collect_callsites):
21  collect_callsites(collect_callsites)
22 {
23 }
24 
29 call_grapht::call_grapht(const goto_modelt &goto_model, bool collect_callsites):
30  call_grapht(goto_model.goto_functions, collect_callsites)
31 {
32 }
33 
39  const goto_functionst &goto_functions, bool collect_callsites):
40  collect_callsites(collect_callsites)
41 {
42  forall_goto_functions(f_it, goto_functions)
43  {
44  const irep_idt &function_name = f_it->first;
45  const goto_programt &body = f_it->second.body;
46  nodes.insert(function_name);
47  add(function_name, body);
48  }
49 }
50 
51 static void forall_callsites(
52  const goto_programt &body,
53  std::function<void(goto_programt::const_targett, const irep_idt &)> call_task)
54 {
56  {
57  if(i_it->is_function_call())
58  {
59  const exprt &function_expr=to_code_function_call(i_it->code).function();
60  if(function_expr.id()==ID_symbol)
61  {
62  const irep_idt &callee=to_symbol_expr(function_expr).get_identifier();
63  call_task(i_it, callee);
64  }
65  }
66  }
67 }
68 
75  const goto_functionst &goto_functions,
76  const irep_idt &root,
77  bool collect_callsites):
78  collect_callsites(collect_callsites)
79 {
80  std::stack<irep_idt, std::vector<irep_idt>> pending_stack;
81  pending_stack.push(root);
82 
83  while(!pending_stack.empty())
84  {
85  irep_idt function=pending_stack.top();
86  pending_stack.pop();
87 
88  nodes.insert(function);
89 
90  // if function is not in function_map, assume function has no body
91  const auto &it = goto_functions.function_map.find(function);
92  if(it == goto_functions.function_map.end())
93  continue;
94 
95  const goto_programt &goto_program = it->second.body;
96 
98  goto_program,
99  [&](goto_programt::const_targett i_it, const irep_idt &callee)
100  {
101  add(function, callee, i_it);
102  if(edges.find(callee)==edges.end())
103  pending_stack.push(callee);
104  }
105  ); // NOLINT
106  }
107 }
108 
115  const goto_modelt &goto_model,
116  const irep_idt &root,
117  bool collect_callsites):
118  call_grapht(goto_model.goto_functions, root, collect_callsites)
119 {
120 }
121 
123  const irep_idt &function,
124  const goto_programt &body)
125 {
127  body,
128  [&](goto_programt::const_targett i_it, const irep_idt &callee)
129  {
130  add(function, callee, i_it);
131  }
132  ); // NOLINT
133 }
134 
139  const irep_idt &caller,
140  const irep_idt &callee)
141 {
142  edges.insert({caller, callee});
143  nodes.insert(caller);
144  nodes.insert(callee);
145 }
146 
153  const irep_idt &caller,
154  const irep_idt &callee,
155  locationt callsite)
156 {
157  add(caller, callee);
159  callsites[{caller, callee}].insert(callsite);
160 }
161 
165 {
166  call_grapht result;
167  result.nodes = nodes;
168  for(const auto &caller_callee : edges)
169  result.add(caller_callee.second, caller_callee.first);
170  return result;
171 }
172 
176 {
179 
180 public:
181  std::unordered_map<irep_idt, node_indext> function_indices;
182 
184  graph(graph)
185  {
186  }
187 
188  node_indext operator[](const irep_idt &function)
189  {
190  auto findit=function_indices.insert({function, 0});
191  if(findit.second)
192  {
193  node_indext new_index=graph.add_node();
194  findit.first->second=new_index;
195  graph[new_index].function=function;
196  }
197  return findit.first->second;
198  }
199 };
200 
209 {
211  function_indicest function_indices(ret);
212 
213  // To make sure we include unreachable functions we first create indices
214  // for all nodes in the graph
215  for(const irep_idt &function_name : nodes)
216  function_indices[function_name];
217 
218  for(const auto &edge : edges)
219  {
220  auto a_index=function_indices[edge.first];
221  auto b_index=function_indices[edge.second];
222  // Check then create the edge like this to avoid copying the callsites
223  // set once per parallel edge, which could be costly if there are many.
224  if(!ret.has_edge(a_index, b_index))
225  {
226  ret.add_edge(a_index, b_index);
228  ret[a_index].out[b_index].callsites=callsites.at(edge);
229  }
230  }
231 
232  ret.nodes_by_name=std::move(function_indices.function_indices);
233  return ret;
234 }
235 
240 std::string call_grapht::format_callsites(const edget &edge) const
241 {
243  std::string ret="{";
244  for(const locationt &loc : callsites.at(edge))
245  {
246  if(ret.size()>1)
247  ret+=", ";
248  ret+=std::to_string(loc->location_number);
249  }
250  ret+='}';
251  return ret;
252 }
253 
254 void call_grapht::output_dot(std::ostream &out) const
255 {
256  out << "digraph call_graph {\n";
257 
258  for(const auto &edge : edges)
259  {
260  out << " \"" << edge.first << "\" -> "
261  << "\"" << edge.second << "\" "
262  << " [arrowhead=\"vee\"";
264  out << " label=\"" << format_callsites(edge) << "\"";
265  out << "];\n";
266  }
267 
268  out << "}\n";
269 }
270 
271 void call_grapht::output(std::ostream &out) const
272 {
273  for(const auto &edge : edges)
274  {
275  out << edge.first << " -> " << edge.second << "\n";
277  out << " (callsites: " << format_callsites(edge) << ")\n";
278  }
279 }
280 
281 void call_grapht::output_xml(std::ostream &out) const
282 {
283  // Note I don't implement callsite output here; I'll leave that
284  // to the first interested XML user.
286  out << "<!-- XML call-graph representation does not document callsites yet."
287  " If you need this, edit call_grapht::output_xml -->\n";
288  for(const auto &edge : edges)
289  {
290  out << "<call_graph_edge caller=\"";
291  xmlt::escape_attribute(id2string(edge.first), out);
292  out << "\" callee=\"";
293  xmlt::escape_attribute(id2string(edge.second), out);
294  out << "\">\n";
295  }
296 }
297 
299  const irep_idt &function) const
300 {
301  auto findit=nodes_by_name.find(function);
302  if(findit==nodes_by_name.end())
303  return optionalt<node_indext>();
304  else
305  return findit->second;
306 }
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::collect_callsites
bool collect_callsites
Definition: call_graph.h:164
forall_callsites
static void forall_callsites(const goto_programt &body, std::function< void(goto_programt::const_targett, const irep_idt &)> call_task)
Definition: call_graph.cpp:51
call_grapht::get_inverted
call_grapht get_inverted() const
Returns an inverted copy of this call graph.
Definition: call_graph.cpp:164
function_indicest
Helper class that maintains a map from function name to grapht node index and adds nodes to the graph...
Definition: call_graph.cpp:176
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
grapht::has_edge
bool has_edge(node_indext i, node_indext j) const
Definition: graph.h:193
call_grapht::call_grapht
call_grapht(bool collect_callsites=false)
Create empty call graph.
Definition: call_graph.cpp:20
function_indicest::graph
call_grapht::directed_grapht & graph
Definition: call_graph.cpp:178
grapht::add_node
node_indext add_node(arguments &&... values)
Definition: graph.h:181
function_indicest::function_indices
std::unordered_map< irep_idt, node_indext > function_indices
Definition: call_graph.cpp:181
exprt
Base class for all expressions.
Definition: expr.h:53
goto_modelt
Definition: goto_model.h:26
call_graph.h
Function Call Graphs.
to_string
std::string to_string(const string_not_contains_constraintt &expr)
Used for debug printing.
Definition: string_constraint.cpp:55
goto_functionst::function_map
function_mapt function_map
Definition: goto_functions.h:27
call_grapht::output_xml
void output_xml(std::ostream &out) const
Definition: call_graph.cpp:281
xml.h
call_grapht::output_dot
void output_dot(std::ostream &out) const
Definition: call_graph.cpp:254
grapht< function_nodet >::node_indext
nodet::node_indext node_indext
Definition: graph.h:174
id2string
const std::string & id2string(const irep_idt &d)
Definition: irep.h:44
PRECONDITION
#define PRECONDITION(CONDITION)
Definition: invariant.h:464
symbol_exprt::get_identifier
const irep_idt & get_identifier() const
Definition: std_expr.h:111
call_grapht::directed_grapht
Directed graph representation of this call graph.
Definition: call_graph.h:135
function_indicest::function_indicest
function_indicest(call_grapht::directed_grapht &graph)
Definition: call_graph.cpp:183
xmlt::escape_attribute
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:116
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
to_symbol_expr
const symbol_exprt & to_symbol_expr(const exprt &expr)
Cast an exprt to a symbol_exprt.
Definition: std_expr.h:177
irept::id
const irep_idt & id() const
Definition: irep.h:418
to_code_function_call
const code_function_callt & to_code_function_call(const codet &code)
Definition: std_code.h:1294
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
grapht::add_edge
void add_edge(node_indext a, node_indext b)
Definition: graph.h:233
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
grapht::out
const edgest & out(node_indext n) const
Definition: graph.h:228
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::edget
std::pair< irep_idt, irep_idt > edget
Type of a call graph edge in edgest
Definition: call_graph.h:90
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
function_indicest::operator[]
node_indext operator[](const irep_idt &function)
Definition: call_graph.cpp:188
call_grapht::output
void output(std::ostream &out) const
Definition: call_graph.cpp:271
goto_programt
A generic container class for the GOTO intermediate representation of one function.
Definition: goto_program.h:73
forall_goto_functions
#define forall_goto_functions(it, functions)
Definition: goto_functions.h:122
function_indicest::node_indext
call_grapht::directed_grapht::node_indext node_indext
Definition: call_graph.cpp:177
goto_programt::const_targett
instructionst::const_iterator const_targett
Definition: goto_program.h:580
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
std_expr.h
API to expression classes.
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
code_function_callt::function
exprt & function()
Definition: std_code.h:1218
forall_goto_program_instructions
#define forall_goto_program_instructions(it, program)
Definition: goto_program.h:1196