call graph helper functions

polgreen · polgreen · commit de7e1af158a4 · 2018-07-24T10:48:03.000+02:00
diff --git a/src/analyses/call_graph_helpers.cpp b/src/analyses/call_graph_helpers.cpp
@@ -74,7 +74,7 @@ std::set<irep_idt> get_reaching_functions(
 std::set<irep_idt> get_functions_reachable_within_n_steps(
   const call_grapht::directed_grapht &graph,
   const std::set<irep_idt> &start_functions,
-  std::size_t &n)
+  std::size_t n)
 {
   std::vector<std::size_t> start_indices;
   std::set<irep_idt> result;
@@ -91,8 +91,32 @@ std::set<irep_idt> get_functions_reachable_within_n_steps(
 std::set<irep_idt> get_functions_reachable_within_n_steps(
   const call_grapht::directed_grapht &graph,
   const irep_idt &start_function,
-  std::size_t &n)
+  std::size_t n)
 {
-  std::set<irep_idt> start_functions({ start_function });
+  std::set<irep_idt> start_functions({start_function});
   return get_functions_reachable_within_n_steps(graph, start_functions, n);
 }
+
+void disconnect_unreachable_functions(
+  call_grapht::directed_grapht &graph,
+  const irep_idt &function)
+{
+  graph.disconnect_unreachable(*(graph.get_node_index(function)));
+}
+
+std::list<irep_idt> get_shortest_function_path(
+  const call_grapht::directed_grapht &graph,
+  const irep_idt &src,
+  const irep_idt &dest)
+{
+  std::list<irep_idt> result;
+  std::list<std::size_t> path;
+
+  graph.shortest_path(
+    *(graph.get_node_index(src)), *(graph.get_node_index(dest)), path);
+
+  for(const auto &n : path)
+    result.push_back(graph[n].function);
+
+  return result;
+}
diff --git a/src/analyses/call_graph_helpers.h b/src/analyses/call_graph_helpers.h
@@ -59,7 +59,7 @@ std::set<irep_idt> get_reaching_functions(
 std::set<irep_idt> get_functions_reachable_within_n_steps(
   const call_grapht::directed_grapht &graph,
   const std::set<irep_idt> &start_functions,
-  std::size_t &n);
+  std::size_t n);
 
 /// Get either callers or callees reachable from a given
 /// list of functions within N steps
@@ -71,6 +71,27 @@ std::set<irep_idt> get_functions_reachable_within_n_steps(
 std::set<irep_idt> get_functions_reachable_within_n_steps(
   const call_grapht::directed_grapht &graph,
   const irep_idt &start_function,
-  std::size_t &n);
+  std::size_t n);
+
+/// Get list of functions on the shortest path between two functions
+/// \param graph: call graph
+/// \param src: function to start from
+/// \param dest: function to reach
+/// \return list of functions on shortest path
+std::list<irep_idt> get_shortest_function_path(
+  const call_grapht::directed_grapht &graph,
+  const irep_idt &src,
+  const irep_idt &dest);
+
+/// Disconnects all functions in the call graph that are unreachable from
+/// a given start function.
+/// Removing nodes requires re-indexing, so instead we disconnect them, removing
+/// all in and out edges from those nodes.
+/// This speeds up backwards reachability.
+/// \param graph: call graph
+/// \param function: start function
+void disconnect_unreachable_functions(
+  call_grapht::directed_grapht &graph,
+  const irep_idt &function);
 
 #endif
