call_graph.cpp

Go to the documentation of this file.

/*******************************************************************\
 
Module: Function Call Graphs
 
Author: Daniel Kroening, kroening@kroening.com
 
\*******************************************************************/
 
 
#include "call_graph.h"
 
#include <util/xml.h>
 
#include <goto-programs/goto_model.h>
 
call_grapht::call_grapht(bool collect_callsites):
  collect_callsites(collect_callsites)
{
}
 
call_grapht::call_grapht(const goto_modelt &goto_model, bool collect_callsites):
  call_grapht(goto_model.goto_functions, collect_callsites)
{
}
 
call_grapht::call_grapht(
  const goto_functionst &goto_functions, bool collect_callsites):
  collect_callsites(collect_callsites)
{
  for(const auto &gf_entry : goto_functions.function_map)
  {
    const irep_idt &function_name = gf_entry.first;
    const goto_programt &body = gf_entry.second.body;
    nodes.insert(function_name);
    add(function_name, body);
  }
}
 
static void forall_callsites(
  const goto_programt &body,
  std::function<void(goto_programt::const_targett, const irep_idt &)> call_task)
{
  forall_goto_program_instructions(i_it, body)
  {
    if(i_it->is_function_call())
    {
      const exprt &function_expr = i_it->call_function();
      PRECONDITION_WITH_DIAGNOSTICS(
        function_expr.id() == ID_symbol,
        "call graph computation requires function pointer removal");
      const irep_idt &callee = to_symbol_expr(function_expr).get_identifier();
      call_task(i_it, callee);
    }
  }
}
 
call_grapht::call_grapht(
  const goto_functionst &goto_functions,
  const irep_idt &root,
  bool collect_callsites):
  collect_callsites(collect_callsites)
{
  std::stack<irep_idt, std::vector<irep_idt>> pending_stack;
  pending_stack.push(root);
 
  while(!pending_stack.empty())
  {
    irep_idt function=pending_stack.top();
    pending_stack.pop();
 
    nodes.insert(function);
 
    // if function is not in function_map, assume function has no body
    const auto &it = goto_functions.function_map.find(function);
    if(it == goto_functions.function_map.end())
      continue;
 
    const goto_programt &goto_program = it->second.body;
 
    forall_callsites(
      goto_program,
      [&](goto_programt::const_targett i_it, const irep_idt &callee)
      {
        add(function, callee, i_it);
        if(edges.find(callee)==edges.end())
          pending_stack.push(callee);
      }
    ); // NOLINT
  }
}
 
call_grapht::call_grapht(
  const goto_modelt &goto_model,
  const irep_idt &root,
  bool collect_callsites):
  call_grapht(goto_model.goto_functions, root, collect_callsites)
{
}
 
void call_grapht::add(
  const irep_idt &function,
  const goto_programt &body)
{
  forall_callsites(
    body,
    [&](goto_programt::const_targett i_it, const irep_idt &callee)
    {
      add(function, callee, i_it);
    }
  ); // NOLINT
}
 
void call_grapht::add(
  const irep_idt &caller,
  const irep_idt &callee)
{
  edges.insert({caller, callee});
  nodes.insert(caller);
  nodes.insert(callee);
}
 
void call_grapht::add(
  const irep_idt &caller,
  const irep_idt &callee,
  locationt callsite)
{
  add(caller, callee);
  if(collect_callsites)
    callsites[{caller, callee}].insert(callsite);
}
 
call_grapht call_grapht::get_inverted() const
{
  call_grapht result;
  result.nodes = nodes;
  for(const auto &caller_callee : edges)
    result.add(caller_callee.second, caller_callee.first);
  return result;
}
 
class function_indicest
{
  typedef call_grapht::directed_grapht::node_indext node_indext;
  call_grapht::directed_grapht &graph;
 
public:
  std::unordered_map<irep_idt, node_indext> function_indices;
 
  explicit function_indicest(call_grapht::directed_grapht &graph):
    graph(graph)
  {
  }
 
  node_indext operator[](const irep_idt &function)
  {
    auto findit=function_indices.insert({function, 0});
    if(findit.second)
    {
      node_indext new_index=graph.add_node();
      findit.first->second=new_index;
      graph[new_index].function=function;
    }
    return findit.first->second;
  }
};
 
call_grapht::directed_grapht call_grapht::get_directed_graph() const
{
  call_grapht::directed_grapht ret;
  function_indicest function_indices(ret);
 
  // To make sure we include unreachable functions we first create indices
  // for all nodes in the graph
  for(const irep_idt &function_name : nodes)
    function_indices[function_name];
 
  for(const auto &edge : edges)
  {
    auto a_index=function_indices[edge.first];
    auto b_index=function_indices[edge.second];
    // Check then create the edge like this to avoid copying the callsites
    // set once per parallel edge, which could be costly if there are many.
    if(!ret.has_edge(a_index, b_index))
    {
      ret.add_edge(a_index, b_index);
      if(collect_callsites)
        ret[a_index].out[b_index].callsites=callsites.at(edge);
    }
  }
 
  ret.nodes_by_name=std::move(function_indices.function_indices);
  return ret;
}
 
std::string call_grapht::format_callsites(const edget &edge) const
{
  PRECONDITION(collect_callsites);
  std::string ret="{";
  for(const locationt &loc : callsites.at(edge))
  {
    if(ret.size()>1)
      ret+=", ";
    ret+=std::to_string(loc->location_number);
  }
  ret+='}';
  return ret;
}
 
void call_grapht::output_dot(std::ostream &out) const
{
  out << "digraph call_graph {\n";
 
  for(const auto &edge : edges)
  {
    out << "  \"" << edge.first << "\" -> "
        << "\"" << edge.second << "\" "
        << " [arrowhead=\"vee\"";
    if(collect_callsites)
      out << " label=\"" << format_callsites(edge) << "\"";
    out << "];\n";
  }
 
  out << "}\n";
}
 
void call_grapht::output(std::ostream &out) const
{
  for(const auto &edge : edges)
  {
    out << edge.first << " -> " << edge.second << "\n";
    if(collect_callsites)
      out << "  (callsites: " << format_callsites(edge) << ")\n";
  }
}
 
void call_grapht::output_xml(std::ostream &out) const
{
  // Note I don't implement callsite output here; I'll leave that
  // to the first interested XML user.
  if(collect_callsites)
    out << "<!-- XML call-graph representation does not document callsites yet."
      " If you need this, edit call_grapht::output_xml -->\n";
  for(const auto &edge : edges)
  {
    out << "<call_graph_edge caller=\"";
    xmlt::escape_attribute(id2string(edge.first), out);
    out << "\" callee=\"";
    xmlt::escape_attribute(id2string(edge.second), out);
    out << "\">\n";
  }
}
 
std::optional<std::size_t>
call_grapht::directed_grapht::get_node_index(const irep_idt &function) const
{
  auto findit=nodes_by_name.find(function);
  if(findit==nodes_by_name.end())
    return std::optional<node_indext>();
  else
    return findit->second;
}