-
Notifications
You must be signed in to change notification settings - Fork 273
/
Copy pathcall_graph_helpers.cpp
122 lines (101 loc) · 3.55 KB
/
call_graph_helpers.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/*******************************************************************\
Module: Function Call Graph Helpers
Author: Chris Smowton, [email protected]
\*******************************************************************/
/// \file
/// Function Call Graph Helpers
#include "call_graph_helpers.h"
/// Get either callers or callees of a given function
/// \param graph: call graph
/// \param function: function to query
/// \param forwards: if true, get callees; otherwise get callers.
static std::set<irep_idt> get_neighbours(
const call_grapht::directed_grapht &graph,
const irep_idt &function,
bool forwards)
{
std::set<irep_idt> result;
const auto &fnode = graph[*(graph.get_node_index(function))];
const auto &neighbours = forwards ? fnode.out : fnode.in;
for(const auto &succ_edge : neighbours)
result.insert(graph[succ_edge.first].function);
return result;
}
std::set<irep_idt> get_callees(
const call_grapht::directed_grapht &graph, const irep_idt &function)
{
return get_neighbours(graph, function, true);
}
std::set<irep_idt> get_callers(
const call_grapht::directed_grapht &graph, const irep_idt &function)
{
return get_neighbours(graph, function, false);
}
/// Get either reachable functions or functions that can reach a given function.
/// In both cases the query function itself is included.
/// \param graph: call graph
/// \param function: function to query
/// \param forwards: if true, get reachable functions; otherwise get functions
/// that can reach the given function.
static std::set<irep_idt> get_connected_functions(
const call_grapht::directed_grapht &graph,
const irep_idt &function,
bool forwards)
{
std::vector<call_grapht::directed_grapht::node_indext> connected_nodes =
graph.get_reachable(*(graph.get_node_index(function)), forwards);
std::set<irep_idt> result;
for(const auto i : connected_nodes)
result.insert(graph[i].function);
return result;
}
std::set<irep_idt> get_reachable_functions(
const call_grapht::directed_grapht &graph, const irep_idt &function)
{
return get_connected_functions(graph, function, true);
}
std::set<irep_idt> get_reaching_functions(
const call_grapht::directed_grapht &graph, const irep_idt &function)
{
return get_connected_functions(graph, function, false);
}
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::vector<std::size_t> start_indices;
std::set<irep_idt> result;
for(const auto &func : start_functions)
start_indices.push_back(*(graph.get_node_index(func)));
for(const auto &index : graph.depth_limited_search(start_indices, n))
result.insert(graph[index].function);
return result;
}
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::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;
}