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();
88  goto_functions.function_map.at(function).body;
89 
90  nodes.insert(function);
91 
94  [&](goto_programt::const_targett i_it, const irep_idt &callee)
95  {
96  add(function, callee, i_it);
97  if(edges.find(callee)==edges.end())
98  pending_stack.push(callee);
99  }
100  ); // NOLINT
101  }
102 }
103 
110  const goto_modelt &goto_model,
111  const irep_idt &root,
112  bool collect_callsites):
113  call_grapht(goto_model.goto_functions, root, collect_callsites)
114 {
115 }
116 
118  const irep_idt &function,
119  const goto_programt &body)
120 {
122  body,
123  [&](goto_programt::const_targett i_it, const irep_idt &callee)
124  {
125  add(function, callee, i_it);
126  }
127  ); // NOLINT
128 }
129 
134  const irep_idt &caller,
135  const irep_idt &callee)
136 {
137  edges.insert({caller, callee});
138  nodes.insert(caller);
139  nodes.insert(callee);
140 }
141 
148  const irep_idt &caller,
149  const irep_idt &callee,
150  locationt callsite)
151 {
152  add(caller, callee);
154  callsites[{caller, callee}].insert(callsite);
155 }
156 
160 {
161  call_grapht result;
162  result.nodes = nodes;
163  for(const auto &caller_callee : edges)
164  result.add(caller_callee.second, caller_callee.first);
165  return result;
166 }
167 
171 {
174 
175 public:
176  std::unordered_map<irep_idt, node_indext> function_indices;
177 
179  graph(graph)
180  {
181  }
182 
183  node_indext operator[](const irep_idt &function)
184  {
185  auto findit=function_indices.insert({function, 0});
186  if(findit.second)
187  {
188  node_indext new_index=graph.add_node();
189  findit.first->second=new_index;
190  graph[new_index].function=function;
191  }
192  return findit.first->second;
193  }
194 };
195 
204 {
206  function_indicest function_indices(ret);
207 
208  // To make sure we include unreachable functions we first create indices
209  // for all nodes in the graph
210  for(const irep_idt &function_name : nodes)
211  function_indices[function_name];
212 
213  for(const auto &edge : edges)
214  {
215  auto a_index=function_indices[edge.first];
216  auto b_index=function_indices[edge.second];
217  // Check then create the edge like this to avoid copying the callsites
218  // set once per parallel edge, which could be costly if there are many.
219  if(!ret.has_edge(a_index, b_index))
220  {
221  ret.add_edge(a_index, b_index);
223  ret[a_index].out[b_index].callsites=callsites.at(edge);
224  }
225  }
226 
227  ret.nodes_by_name=std::move(function_indices.function_indices);
228  return ret;
229 }
230 
235 std::string call_grapht::format_callsites(const edget &edge) const
236 {
238  std::string ret="{";
239  for(const locationt &loc : callsites.at(edge))
240  {
241  if(ret.size()>1)
242  ret+=", ";
243  ret+=std::to_string(loc->location_number);
244  }
245  ret+='}';
246  return ret;
247 }
248 
249 void call_grapht::output_dot(std::ostream &out) const
250 {
251  out << "digraph call_graph {\n";
252 
253  for(const auto &edge : edges)
254  {
255  out << " \"" << edge.first << "\" -> "
256  << "\"" << edge.second << "\" "
257  << " [arrowhead=\"vee\"";
259  out << " label=\"" << format_callsites(edge) << "\"";
260  out << "];\n";
261  }
262 
263  out << "}\n";
264 }
265 
266 void call_grapht::output(std::ostream &out) const
267 {
268  for(const auto &edge : edges)
269  {
270  out << edge.first << " -> " << edge.second << "\n";
272  out << " (callsites: " << format_callsites(edge) << ")\n";
273  }
274 }
275 
276 void call_grapht::output_xml(std::ostream &out) const
277 {
278  // Note I don't implement callsite output here; I'll leave that
279  // to the first interested XML user.
281  out << "<!-- XML call-graph representation does not document callsites yet."
282  " If you need this, edit call_grapht::output_xml -->\n";
283  for(const auto &edge : edges)
284  {
285  out << "<call_graph_edge caller=\"";
286  xmlt::escape_attribute(id2string(edge.first), out);
287  out << "\" callee=\"";
288  xmlt::escape_attribute(id2string(edge.second), out);
289  out << "\">\n";
290  }
291 }
292 
294  const irep_idt &function) const
295 {
296  auto findit=nodes_by_name.find(function);
297  if(findit==nodes_by_name.end())
298  return optionalt<node_indext>();
299  else
300  return findit->second;
301 }
#define loc()
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
call_grapht::directed_grapht::node_indext node_indext
Definition: call_graph.cpp:172
const std::string & id2string(const irep_idt &d)
Definition: irep.h:43
goto_programt::const_targett locationt
Type of a callsite stored in member callsites
Definition: call_graph.h:76
const irep_idt & get_identifier() const
Definition: std_expr.h:128
Function Call Graphs.
function_mapt function_map
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_indext operator[](const irep_idt &function)
Definition: call_graph.cpp:183
bool has_edge(node_indext i, node_indext j) const
Definition: graph.h:158
const irep_idt & id() const
Definition: irep.h:189
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
API to expression classes.
void output_dot(std::ostream &out) const
Definition: call_graph.cpp:249
const edgest & out(node_indext n) const
Definition: graph.h:193
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
#define PRECONDITION(CONDITION)
Definition: invariant.h:230
callsitest callsites
Map from call-graph edges to a set of callsites that make the given call.
Definition: call_graph.h:94
const symbol_exprt & to_symbol_expr(const exprt &expr)
Cast a generic exprt to a symbol_exprt.
Definition: std_expr.h:210
nodet::node_indext node_indext
Definition: graph.h:140
void output(std::ostream &out) const
Definition: call_graph.cpp:266
A generic container class for the GOTO intermediate representation of one function.
Definition: goto_program.h:70
node_indext add_node()
Definition: graph.h:146
exprt & function()
Definition: std_code.h:848
function_indicest(call_grapht::directed_grapht &graph)
Definition: call_graph.cpp:178
Base class for all expressions.
Definition: expr.h:42
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
std::string to_string(const string_constraintt &expr)
Used for debug printing.
void add_edge(node_indext a, node_indext b)
Definition: graph.h:198
goto_programt & goto_program
Definition: cover.cpp:63
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
#define forall_goto_functions(it, functions)
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:115
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
#define forall_goto_program_instructions(it, program)
Definition: goto_program.h:735
call_grapht::directed_grapht & graph
Definition: call_graph.cpp:173
Helper class that maintains a map from function name to grapht node index and adds nodes to the graph...
Definition: call_graph.cpp:170
std::unordered_map< irep_idt, node_indext > function_indices
Definition: call_graph.cpp:176
const code_function_callt & to_code_function_call(const codet &code)
Definition: std_code.h:879