cprover
compute_called_functions.cpp
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Query Called Functions
4 
5 Author: Daniel Kroening, kroening@kroening.com
6 
7 \*******************************************************************/
8 
11 
13 
14 #include <util/pointer_expr.h>
15 #include <util/std_expr.h>
16 
19  const exprt &src,
20  std::unordered_set<irep_idt> &address_taken)
21 {
22  forall_operands(it, src)
23  compute_address_taken_functions(*it, address_taken);
24 
25  if(src.id() == ID_address_of)
26  {
27  const address_of_exprt &address = to_address_of_expr(src);
28 
29  if(
30  address.type().id() == ID_pointer &&
31  address.type().subtype().id() == ID_code)
32  {
33  const exprt &target = address.object();
34  if(target.id() == ID_symbol)
35  address_taken.insert(to_symbol_expr(target).get_identifier());
36  }
37  }
38 }
39 
42  const exprt &src,
43  std::unordered_set<irep_idt> &address_taken)
44 {
45  forall_operands(it, src)
46  compute_functions(*it, address_taken);
47 
48  if(src.type().id()==ID_code &&
49  src.id()==ID_symbol)
50  address_taken.insert(to_symbol_expr(src).get_identifier());
51 }
52 
55  const goto_programt &goto_program,
56  std::unordered_set<irep_idt> &address_taken)
57 {
58  for(const auto &i : goto_program.instructions)
59  {
60  i.apply([&address_taken](const exprt &expr) {
61  compute_address_taken_functions(expr, address_taken);
62  });
63  }
64 }
65 
68  const goto_functionst &goto_functions,
69  std::unordered_set<irep_idt> &address_taken)
70 {
71  for(const auto &gf_entry : goto_functions.function_map)
72  compute_address_taken_functions(gf_entry.second.body, address_taken);
73 }
74 
76 std::unordered_set<irep_idt>
78 {
79  std::unordered_set<irep_idt> address_taken;
80  compute_address_taken_functions(goto_functions, address_taken);
81  return address_taken;
82 }
83 
85 std::unordered_set<irep_idt>
87 {
88  std::unordered_set<irep_idt> working_queue;
89  std::unordered_set<irep_idt> functions;
90 
91  // start from entry point
92  working_queue.insert(goto_functions.entry_point());
93 
94  while(!working_queue.empty())
95  {
96  irep_idt id=*working_queue.begin();
97  working_queue.erase(working_queue.begin());
98 
99  if(!functions.insert(id).second)
100  continue;
101 
102  const goto_functionst::function_mapt::const_iterator f_it=
103  goto_functions.function_map.find(id);
104 
105  if(f_it==goto_functions.function_map.end())
106  continue;
107 
108  const goto_programt &program=
109  f_it->second.body;
110 
111  compute_address_taken_functions(program, working_queue);
112 
113  for(const auto &instruction : program.instructions)
114  {
115  if(instruction.is_function_call())
116  {
118  to_code_function_call(instruction.code).function(), working_queue);
119  }
120  }
121  }
122 
123  return functions;
124 }
125 
127 std::unordered_set<irep_idt>
129 {
130  return compute_called_functions(goto_model.goto_functions);
131 }
dstringt
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:37
typet::subtype
const typet & subtype() const
Definition: type.h:47
address_of_exprt::object
exprt & object()
Definition: pointer_expr.h:209
exprt
Base class for all expressions.
Definition: expr.h:54
goto_modelt
Definition: goto_model.h:26
goto_functionst::function_map
function_mapt function_map
Definition: goto_functions.h:27
compute_called_functions
std::unordered_set< irep_idt > compute_called_functions(const goto_functionst &goto_functions)
computes the functions that are (potentially) called
Definition: compute_called_functions.cpp:86
compute_functions
void compute_functions(const exprt &src, std::unordered_set< irep_idt > &address_taken)
get all functions in the expression
Definition: compute_called_functions.cpp:41
exprt::type
typet & type()
Return the type of the expression.
Definition: expr.h:82
forall_operands
#define forall_operands(it, expr)
Definition: expr.h:18
pointer_expr.h
API to expression classes for Pointers.
to_symbol_expr
const symbol_exprt & to_symbol_expr(const exprt &expr)
Cast an exprt to a symbol_exprt.
Definition: std_expr.h:190
irept::id
const irep_idt & id() const
Definition: irep.h:407
to_code_function_call
const code_function_callt & to_code_function_call(const codet &code)
Definition: std_code.h:1326
goto_programt::instructions
instructionst instructions
The list of instructions in the goto program.
Definition: goto_program.h:556
goto_functionst
A collection of goto functions.
Definition: goto_functions.h:23
goto_modelt::goto_functions
goto_functionst goto_functions
GOTO functions.
Definition: goto_model.h:33
compute_address_taken_functions
void compute_address_taken_functions(const exprt &src, std::unordered_set< irep_idt > &address_taken)
get all functions whose address is taken
Definition: compute_called_functions.cpp:18
goto_programt
A generic container class for the GOTO intermediate representation of one function.
Definition: goto_program.h:74
to_address_of_expr
const address_of_exprt & to_address_of_expr(const exprt &expr)
Cast an exprt to an address_of_exprt.
Definition: pointer_expr.h:237
compute_called_functions.h
Query Called Functions.
goto_functionst::entry_point
static irep_idt entry_point()
Get the identifier of the entry point to a goto model.
Definition: goto_functions.h:90
address_of_exprt
Operator to return the address of an object.
Definition: pointer_expr.h:200
std_expr.h
API to expression classes.
code_function_callt::function
exprt & function()
Definition: std_code.h:1250