cprover
Loading...
Searching...
No Matches
remove_function_pointers.cpp
Go to the documentation of this file.
1/*******************************************************************\
2
3Module: Program Transformation
4
5Author: Daniel Kroening, kroening@kroening.com
6
7\*******************************************************************/
8
11
13
14#include <util/arith_tools.h>
15#include <util/byte_operators.h>
16#include <util/c_types.h>
17#include <util/fresh_symbol.h>
18#include <util/invariant.h>
19#include <util/message.h>
20#include <util/pointer_expr.h>
23#include <util/std_code.h>
24#include <util/std_expr.h>
25#include <util/string_utils.h>
26
28
30#include "goto_model.h"
32#include "remove_skip.h"
33
35{
36public:
38 message_handlert &_message_handler,
39 symbol_tablet &_symbol_table,
41 const goto_functionst &goto_functions);
42
43 void operator()(goto_functionst &goto_functions);
44
46 goto_programt &goto_program,
47 const irep_idt &function_id);
48
49protected:
53
54 // We can optionally halt the FP removal if we aren't able to use
55 // remove_const_function_pointerst to successfully narrow to a small
56 // subset of possible functions and just leave the function pointer
57 // as it is.
58 // This can be activated in goto-instrument using
59 // --remove-const-function-pointers instead of --remove-function-pointers
61
69 goto_programt &goto_program,
70 const irep_idt &function_id,
72
73 std::unordered_set<irep_idt> address_taken;
74
75 typedef std::map<irep_idt, code_typet> type_mapt;
77};
78
80 message_handlert &_message_handler,
81 symbol_tablet &_symbol_table,
82 bool only_resolve_const_fps,
83 const goto_functionst &goto_functions)
84 : message_handler(_message_handler),
85 ns(_symbol_table),
86 symbol_table(_symbol_table),
87 only_resolve_const_fps(only_resolve_const_fps)
88{
89 for(const auto &s : symbol_table.symbols)
91
93
94 // build type map
95 for(const auto &gf_entry : goto_functions.function_map)
96 {
97 type_map.emplace(
98 gf_entry.first, to_code_type(ns.lookup(gf_entry.first).type));
99 }
100}
101
103 const typet &call_type,
104 const typet &function_type,
105 const namespacet &ns)
106{
107 if(call_type == function_type)
108 return true;
109
110 // any integer-vs-enum-vs-pointer is ok
111 if(
112 call_type.id() == ID_signedbv || call_type.id() == ID_unsignedbv ||
113 call_type.id() == ID_bool || call_type.id() == ID_c_bool ||
114 call_type.id() == ID_c_enum_tag || call_type.id() == ID_c_enum ||
115 call_type.id() == ID_pointer)
116 {
117 return function_type.id() == ID_signedbv ||
118 function_type.id() == ID_unsignedbv ||
119 function_type.id() == ID_bool || function_type.id() == ID_c_bool ||
120 function_type.id() == ID_pointer ||
121 function_type.id() == ID_c_enum ||
122 function_type.id() == ID_c_enum_tag;
123 }
124
125 return pointer_offset_bits(call_type, ns) ==
126 pointer_offset_bits(function_type, ns);
127}
128
130 bool return_value_used,
131 const code_typet &call_type,
132 const code_typet &function_type,
133 const namespacet &ns)
134{
135 // we are willing to ignore anything that's returned
136 // if we call with 'void'
137 if(!return_value_used)
138 {
139 }
140 else if(call_type.return_type() == empty_typet())
141 {
142 // ok
143 }
144 else
145 {
147 call_type.return_type(), function_type.return_type(), ns))
148 return false;
149 }
150
151 // let's look at the parameters
152 const code_typet::parameterst &call_parameters=call_type.parameters();
153 const code_typet::parameterst &function_parameters=function_type.parameters();
154
155 if(function_type.has_ellipsis() &&
156 function_parameters.empty())
157 {
158 // always ok
159 }
160 else if(call_type.has_ellipsis() &&
161 call_parameters.empty())
162 {
163 // always ok
164 }
165 else
166 {
167 // we are quite strict here, could be much more generous
168 if(call_parameters.size()!=function_parameters.size())
169 return false;
170
171 for(std::size_t i=0; i<call_parameters.size(); i++)
173 call_parameters[i].type(), function_parameters[i].type(), ns))
174 return false;
175 }
176
177 return true;
178}
179
180static void fix_argument_types(code_function_callt &function_call)
181{
182 const code_typet &code_type = to_code_type(function_call.function().type());
183
184 const code_typet::parameterst &function_parameters=
185 code_type.parameters();
186
187 code_function_callt::argumentst &call_arguments=
188 function_call.arguments();
189
190 for(std::size_t i=0; i<function_parameters.size(); i++)
191 {
192 if(i<call_arguments.size())
193 {
194 if(call_arguments[i].type() != function_parameters[i].type())
195 {
196 call_arguments[i] = make_byte_extract(
197 call_arguments[i],
199 function_parameters[i].type());
200 }
201 }
202 }
203}
204
205static void fix_return_type(
206 const irep_idt &in_function_id,
207 code_function_callt &function_call,
208 symbol_tablet &symbol_table,
209 goto_programt &dest)
210{
211 // are we returning anything at all?
212 if(function_call.lhs().is_nil())
213 return;
214
215 const code_typet &code_type = to_code_type(function_call.function().type());
216
217 // type already ok?
218 if(function_call.lhs().type() == code_type.return_type())
219 return;
220
221 const namespacet ns(symbol_table);
222 const symbolt &function_symbol =
223 ns.lookup(to_symbol_expr(function_call.function()).get_identifier());
224
225 symbolt &tmp_symbol = get_fresh_aux_symbol(
226 code_type.return_type(),
227 id2string(in_function_id),
228 "tmp_return_val_" + id2string(function_symbol.base_name),
229 function_call.source_location(),
230 function_symbol.mode,
231 symbol_table);
232
233 const symbol_exprt tmp_symbol_expr = tmp_symbol.symbol_expr();
234
235 exprt old_lhs=function_call.lhs();
236 function_call.lhs()=tmp_symbol_expr;
237
239 old_lhs,
241 tmp_symbol_expr, from_integer(0, c_index_type()), old_lhs.type()),
242 function_call.source_location())));
243}
244
246 goto_programt &goto_program,
247 const irep_idt &function_id,
249{
250 const auto &function = to_dereference_expr(as_const(*target).call_function());
251
252 // this better have the right type
253 code_typet call_type=to_code_type(function.type());
254
255 // refine the type in case the forward declaration was incomplete
256 if(call_type.has_ellipsis() &&
257 call_type.parameters().empty())
258 {
259 call_type.remove_ellipsis();
260 for(const auto &argument : as_const(*target).call_arguments())
261 {
262 call_type.parameters().push_back(code_typet::parametert(argument.type()));
263 }
264 }
265
266 bool found_functions;
267
268 const exprt &pointer = function.pointer();
270 does_remove_constt const_removal_check(goto_program);
271 const auto does_remove_const = const_removal_check();
273 if(does_remove_const.first)
274 {
275 log.warning().source_location = does_remove_const.second;
276 log.warning() << "cast from const to non-const pointer found, "
277 << "only worst case function pointer removal will be done."
278 << messaget::eom;
279 found_functions=false;
280 }
281 else
282 {
284 log.get_message_handler(), ns, symbol_table);
285
286 found_functions=fpr(pointer, functions);
287
288 // if found_functions is false, functions should be empty
289 // however, it is possible for found_functions to be true and functions
290 // to be empty (this happens if the pointer can only resolve to the null
291 // pointer)
292 CHECK_RETURN(found_functions || functions.empty());
293
294 if(functions.size()==1)
295 {
296 target->call_function() = *functions.cbegin();
297 return;
298 }
299 }
300
301 if(!found_functions)
302 {
304 {
305 // If this mode is enabled, we only remove function pointers
306 // that we can resolve either to an exact function, or an exact subset
307 // (e.g. a variable index in a constant array).
308 // Since we haven't found functions, we would now resort to
309 // replacing the function pointer with any function with a valid signature
310 // Since we don't want to do that, we abort.
311 return;
312 }
313
314 bool return_value_used = as_const(*target).call_lhs().is_not_nil();
315
316 // get all type-compatible functions
317 // whose address is ever taken
318 for(const auto &t : type_map)
319 {
320 // address taken?
321 if(address_taken.find(t.first)==address_taken.end())
322 continue;
323
324 // type-compatible?
326 return_value_used, call_type, t.second, ns))
327 continue;
328
329 if(t.first=="pthread_mutex_cleanup")
330 continue;
331
332 symbol_exprt expr(t.first, t.second);
333 functions.insert(expr);
334 }
335 }
336
340 goto_program,
341 function_id,
342 target,
343 functions);
344}
345
347 const std::unordered_set<symbol_exprt, irep_hash> &candidates)
348{
349 std::stringstream comment;
350
351 comment << "dereferenced function pointer must be ";
352
353 if(candidates.size() == 1)
354 {
355 comment << candidates.begin()->get_identifier();
356 }
357 else if(candidates.empty())
358 {
359 comment.str("no candidates for dereferenced function pointer");
360 }
361 else
362 {
363 comment << "one of [";
364
366 comment,
367 candidates.begin(),
368 candidates.end(),
369 ", ",
370 [](const symbol_exprt &s) { return s.get_identifier(); });
371
372 comment << ']';
373 }
374
375 return comment.str();
376}
377
379 message_handlert &message_handler,
380 symbol_tablet &symbol_table,
381 goto_programt &goto_program,
382 const irep_idt &function_id,
384 const std::unordered_set<symbol_exprt, irep_hash> &functions)
385{
386 const exprt &function = target->call_function();
387 const exprt &pointer = to_dereference_expr(function).pointer();
388
389 // the final target is a skip
390 goto_programt final_skip;
391
392 goto_programt::targett t_final =
393 final_skip.add(goto_programt::make_skip(target->source_location()));
394
395 // build the calls and gotos
396
397 goto_programt new_code_calls;
398 goto_programt new_code_gotos;
399
400 for(const auto &fun : functions)
401 {
402 // call function
403 auto new_call =
404 code_function_callt(target->call_lhs(), fun, target->call_arguments());
405
406 // the signature of the function might not match precisely
407 fix_argument_types(new_call);
408
409 goto_programt tmp;
410 fix_return_type(function_id, new_call, symbol_table, tmp);
411
412 auto call = new_code_calls.add(
413 goto_programt::make_function_call(new_call, target->source_location()));
414 new_code_calls.destructive_append(tmp);
415
416 // goto final
417 new_code_calls.add(goto_programt::make_goto(
418 t_final, true_exprt(), target->source_location()));
419
420 // goto to call
421 const address_of_exprt address_of(fun, pointer_type(fun.type()));
422
423 const auto casted_address =
424 typecast_exprt::conditional_cast(address_of, pointer.type());
425
426 new_code_gotos.add(goto_programt::make_goto(
427 call, equal_exprt(pointer, casted_address), target->source_location()));
428 }
429
430 // fall-through
431 source_locationt annotated_location = target->source_location();
432 annotated_location.set_property_class("pointer dereference");
433 annotated_location.set_comment(function_pointer_assertion_comment(functions));
434 new_code_gotos.add(
435 goto_programt::make_assertion(false_exprt(), annotated_location));
436 new_code_gotos.add(
437 goto_programt::make_assumption(false_exprt(), target->source_location()));
438
439 goto_programt new_code;
440
441 // patch them all together
442 new_code.destructive_append(new_code_gotos);
443 new_code.destructive_append(new_code_calls);
444 new_code.destructive_append(final_skip);
445
446 goto_programt::targett next_target=target;
447 next_target++;
448
449 goto_program.destructive_insert(next_target, new_code);
450
451 // We preserve the original dereferencing to possibly catch
452 // further pointer-related errors.
453 code_expressiont code_expression(function);
454 code_expression.add_source_location()=function.source_location();
455 *target =
456 goto_programt::make_other(code_expression, target->source_location());
457
458 // report statistics
459 messaget log{message_handler};
460 log.statistics().source_location = target->source_location();
461 log.statistics() << "replacing function pointer by " << functions.size()
462 << " possible targets" << messaget::eom;
463
464 // list the names of functions when verbosity is at debug level
465 log.conditional_output(
466 log.debug(), [&functions](messaget::mstreamt &mstream) {
467 mstream << "targets: ";
468
469 bool first = true;
470 for(const auto &function : functions)
471 {
472 if(!first)
473 mstream << ", ";
474
475 mstream << function.get_identifier();
476 first = false;
477 }
478
479 mstream << messaget::eom;
480 });
481}
482
484 goto_programt &goto_program,
485 const irep_idt &function_id)
486{
487 bool did_something=false;
488
489 Forall_goto_program_instructions(target, goto_program)
490 if(target->is_function_call())
491 {
492 if(target->call_function().id() == ID_dereference)
493 {
494 remove_function_pointer(goto_program, function_id, target);
495 did_something=true;
496 }
497 }
498
499 if(did_something)
500 remove_skip(goto_program);
501
502 return did_something;
503}
504
506{
507 bool did_something=false;
508
509 for(goto_functionst::function_mapt::iterator f_it=
510 functions.function_map.begin();
511 f_it!=functions.function_map.end();
512 f_it++)
513 {
514 goto_programt &goto_program=f_it->second.body;
515
516 if(remove_function_pointers(goto_program, f_it->first))
517 did_something=true;
518 }
519
520 if(did_something)
521 functions.compute_location_numbers();
522}
523
525 message_handlert &_message_handler,
526 goto_modelt &goto_model,
527 bool only_remove_const_fps)
528{
530 _message_handler,
531 goto_model.symbol_table,
532 only_remove_const_fps,
533 goto_model.goto_functions);
534
535 rfp(goto_model.goto_functions);
536}
constant_exprt from_integer(const mp_integer &int_value, const typet &type)
const T & as_const(T &value)
Return a reference to the same object but ensures the type is const.
Definition as_const.h:14
byte_extract_exprt make_byte_extract(const exprt &_op, const exprt &_offset, const typet &_type)
Construct a byte_extract_exprt with endianness and byte width matching the current configuration.
Expression classes for byte-level operators.
pointer_typet pointer_type(const typet &subtype)
Definition c_types.cpp:240
bitvector_typet c_index_type()
Definition c_types.cpp:16
Operator to return the address of an object.
A goto_instruction_codet representing an assignment in the program.
codet representation of an expression statement.
Definition std_code.h:1394
goto_instruction_codet representation of a function call statement.
Base type of functions.
Definition std_types.h:539
std::vector< parametert > parameterst
Definition std_types.h:542
const parameterst & parameters() const
Definition std_types.h:655
const typet & return_type() const
Definition std_types.h:645
void remove_ellipsis()
Definition std_types.h:640
bool has_ellipsis() const
Definition std_types.h:611
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition dstring.h:39
The empty type.
Definition std_types.h:51
Equality.
Definition std_expr.h:1306
Base class for all expressions.
Definition expr.h:56
typet & type()
Return the type of the expression.
Definition expr.h:84
const source_locationt & source_location() const
Definition expr.h:223
source_locationt & add_source_location()
Definition expr.h:228
The Boolean constant false.
Definition std_expr.h:3017
A collection of goto functions.
function_mapt function_map
void compute_location_numbers()
symbol_tablet symbol_table
Symbol table.
Definition goto_model.h:31
goto_functionst goto_functions
GOTO functions.
Definition goto_model.h:34
A generic container class for the GOTO intermediate representation of one function.
static instructiont make_assumption(const exprt &g, const source_locationt &l=source_locationt::nil())
void destructive_insert(const_targett target, goto_programt &p)
Inserts the given program p before target.
instructionst::iterator targett
void destructive_append(goto_programt &p)
Appends the given program p to *this. p is destroyed.
static instructiont make_assignment(const code_assignt &_code, const source_locationt &l=source_locationt::nil())
Create an assignment instruction.
static instructiont make_skip(const source_locationt &l=source_locationt::nil())
static instructiont make_function_call(const code_function_callt &_code, const source_locationt &l=source_locationt::nil())
Create a function call instruction.
static instructiont make_other(const goto_instruction_codet &_code, const source_locationt &l=source_locationt::nil())
targett add(instructiont &&instruction)
Adds a given instruction at the end.
static instructiont make_goto(targett _target, const source_locationt &l=source_locationt::nil())
static instructiont make_assertion(const exprt &g, const source_locationt &l=source_locationt::nil())
const irep_idt & id() const
Definition irep.h:396
bool is_nil() const
Definition irep.h:376
Class that provides messages with a built-in verbosity 'level'.
Definition message.h:155
static eomt eom
Definition message.h:297
A namespacet is essentially one or two symbol tables bound together, to allow for symbol lookups in t...
Definition namespace.h:91
bool lookup(const irep_idt &name, const symbolt *&symbol) const override
See documentation for namespace_baset::lookup().
std::unordered_set< symbol_exprt, irep_hash > functionst
remove_function_pointerst(message_handlert &_message_handler, symbol_tablet &_symbol_table, bool only_resolve_const_fps, const goto_functionst &goto_functions)
std::map< irep_idt, code_typet > type_mapt
void operator()(goto_functionst &goto_functions)
void remove_function_pointer(goto_programt &goto_program, const irep_idt &function_id, goto_programt::targett target)
Replace a call to a dynamic function at location target in the given goto-program by determining func...
std::unordered_set< irep_idt > address_taken
bool remove_function_pointers(goto_programt &goto_program, const irep_idt &function_id)
void set_comment(const irep_idt &comment)
void set_property_class(const irep_idt &property_class)
Expression to hold a symbol (variable)
Definition std_expr.h:113
const irep_idt & get_identifier() const
Definition std_expr.h:142
const symbolst & symbols
Read-only field, used to look up symbols given their names.
The symbol table.
Symbol table entry.
Definition symbol.h:28
irep_idt base_name
Base (non-scoped) name.
Definition symbol.h:46
class symbol_exprt symbol_expr() const
Produces a symbol_exprt for a symbol.
Definition symbol.cpp:121
irep_idt mode
Language mode.
Definition symbol.h:49
The Boolean constant true.
Definition std_expr.h:3008
static exprt conditional_cast(const exprt &expr, const typet &type)
Definition std_expr.h:2025
The type of an expression, extends irept.
Definition type.h:29
void compute_address_taken_functions(const exprt &src, std::unordered_set< irep_idt > &address_taken)
get all functions whose address is taken
Query Called Functions.
symbolt & get_fresh_aux_symbol(const typet &type, const std::string &name_prefix, const std::string &basename_prefix, const source_locationt &source_location, const irep_idt &symbol_mode, const namespacet &ns, symbol_table_baset &symbol_table)
Installs a fresh-named symbol with respect to the given namespace ns with the requested name pattern ...
Fresh auxiliary symbol creation.
Symbol Table + CFG.
#define Forall_goto_program_instructions(it, program)
const std::string & id2string(const irep_idt &d)
Definition irep.h:47
API to expression classes for Pointers.
const dereference_exprt & to_dereference_expr(const exprt &expr)
Cast an exprt to a dereference_exprt.
optionalt< mp_integer > pointer_offset_bits(const typet &type, const namespacet &ns)
Pointer Logic.
static std::string comment(const rw_set_baset::entryt &entry, bool write)
static bool arg_is_type_compatible(const typet &call_type, const typet &function_type, const namespacet &ns)
void remove_function_pointer(message_handlert &message_handler, symbol_tablet &symbol_table, goto_programt &goto_program, const irep_idt &function_id, goto_programt::targett target, const std::unordered_set< symbol_exprt, irep_hash > &functions)
Replace a call to a dynamic function at location target in the given goto-program by a case-split ove...
static void fix_return_type(const irep_idt &in_function_id, code_function_callt &function_call, symbol_tablet &symbol_table, goto_programt &dest)
bool function_is_type_compatible(bool return_value_used, const code_typet &call_type, const code_typet &function_type, const namespacet &ns)
Returns true iff call_type can be converted to produce a function call of the same type as function_t...
static std::string function_pointer_assertion_comment(const std::unordered_set< symbol_exprt, irep_hash > &candidates)
static void fix_argument_types(code_function_callt &function_call)
void remove_function_pointers(message_handlert &_message_handler, goto_modelt &goto_model, bool only_remove_const_fps)
Remove Indirect Function Calls.
void remove_skip(goto_programt &goto_program, goto_programt::targett begin, goto_programt::targett end)
remove unnecessary skip statements
Program Transformation.
#define CHECK_RETURN(CONDITION)
Definition invariant.h:495
API to expression classes.
const symbol_exprt & to_symbol_expr(const exprt &expr)
Cast an exprt to a symbol_exprt.
Definition std_expr.h:222
const code_typet & to_code_type(const typet &type)
Cast a typet to a code_typet.
Definition std_types.h:744
Stream & join_strings(Stream &&os, const It b, const It e, const Delimiter &delimiter, TransformFunc &&transform_func)
Prints items to an stream, separated by a constant delimiter.