cprover
remove_const_function_pointers.cpp
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Goto Programs
4 
5 Author: Thomas Kiley, thomas.kiley@diffblue.com
6 
7 \*******************************************************************/
8 
11 
13 
14 #include <util/arith_tools.h>
15 #include <util/format_expr.h>
16 #include <util/namespace.h>
17 #include <util/pointer_expr.h>
18 #include <util/simplify_expr.h>
19 #include <util/std_expr.h>
20 #include <util/symbol_table.h>
21 
22 #define LOG(message, irep) \
23  do \
24  { \
25  log.debug().source_location = irep.source_location(); \
26  log.debug() << message << ": " << format(irep) << messaget::eom; \
27  } while(0)
28 
35  message_handlert &message_handler,
36  const namespacet &ns,
37  const symbol_tablet &symbol_table)
38  : log(message_handler), ns(ns), symbol_table(symbol_table)
39 {}
40 
53  const exprt &base_expression,
54  functionst &out_functions)
55 {
56  // Replace all const symbols with their values
57  exprt non_symbol_expression=replace_const_symbols(base_expression);
58  return try_resolve_function_call(non_symbol_expression, out_functions);
59 }
60 
69  const exprt &expression) const
70 {
71  if(expression.id()==ID_symbol)
72  {
73  if(is_const_expression(expression))
74  {
75  const symbolt &symbol =
76  symbol_table.lookup_ref(to_symbol_expr(expression).get_identifier());
77  if(symbol.type.id()!=ID_code)
78  {
79  const exprt &symbol_value=symbol.value;
80  return replace_const_symbols(symbol_value);
81  }
82  else
83  {
84  return expression;
85  }
86  }
87  else
88  {
89  return expression;
90  }
91  }
92  else
93  {
94  exprt const_symbol_cleared_expr=expression;
95  const_symbol_cleared_expr.operands().clear();
96  for(const exprt &op : expression.operands())
97  {
98  exprt const_symbol_cleared_op=replace_const_symbols(op);
99  const_symbol_cleared_expr.operands().push_back(const_symbol_cleared_op);
100  }
101 
102  return const_symbol_cleared_expr;
103  }
104 }
105 
110  const symbol_exprt &symbol_expr) const
111 {
112  const symbolt &symbol = symbol_table.lookup_ref(symbol_expr.get_identifier());
113  return symbol.value;
114 }
115 
125  const exprt &expr, functionst &out_functions)
126 {
127  PRECONDITION(out_functions.empty());
128  const exprt &simplified_expr=simplify_expr(expr, ns);
129  bool resolved=false;
130  functionst resolved_functions;
131  if(simplified_expr.id()==ID_index)
132  {
133  const index_exprt &index_expr=to_index_expr(simplified_expr);
134  resolved=try_resolve_index_of_function_call(index_expr, resolved_functions);
135  }
136  else if(simplified_expr.id()==ID_member)
137  {
138  const member_exprt &member_expr=to_member_expr(simplified_expr);
139  resolved=try_resolve_member_function_call(member_expr, resolved_functions);
140  }
141  else if(simplified_expr.id()==ID_address_of)
142  {
143  address_of_exprt address_expr=to_address_of_expr(simplified_expr);
145  address_expr, resolved_functions);
146  }
147  else if(simplified_expr.id()==ID_dereference)
148  {
149  const dereference_exprt &deref=to_dereference_expr(simplified_expr);
150  resolved=try_resolve_dereference_function_call(deref, resolved_functions);
151  }
152  else if(simplified_expr.id()==ID_typecast)
153  {
154  typecast_exprt typecast_expr=to_typecast_expr(simplified_expr);
155  resolved=
156  try_resolve_typecast_function_call(typecast_expr, resolved_functions);
157  }
158  else if(simplified_expr.id()==ID_symbol)
159  {
160  if(simplified_expr.type().id()==ID_code)
161  {
162  resolved_functions.insert(to_symbol_expr(simplified_expr));
163  resolved=true;
164  }
165  else
166  {
167  LOG("Non const symbol wasn't squashed", simplified_expr);
168  resolved=false;
169  }
170  }
171  else if(simplified_expr.id()==ID_constant)
172  {
173  if(simplified_expr.is_zero())
174  {
175  // We have the null pointer - no need to throw everything away
176  // but we don't add any functions either
177  resolved=true;
178  }
179  else
180  {
181  LOG("Non-zero constant value found", simplified_expr);
182  resolved=false;
183  }
184  }
185  else
186  {
187  LOG("Unrecognised expression", simplified_expr);
188  resolved=false;
189  }
190 
191  if(resolved)
192  {
193  out_functions.insert(resolved_functions.begin(), resolved_functions.end());
194  return true;
195  }
196  else
197  {
198  return false;
199  }
200 }
201 
209  const expressionst &exprs, functionst &out_functions)
210 {
211  for(const exprt &value : exprs)
212  {
213  functionst potential_out_functions;
214  bool resolved_value=
215  try_resolve_function_call(value, potential_out_functions);
216 
217  if(resolved_value)
218  {
219  out_functions.insert(
220  potential_out_functions.begin(),
221  potential_out_functions.end());
222  }
223  else
224  {
225  LOG("Could not resolve expression in array", value);
226  return false;
227  }
228  }
229  return true;
230 }
231 
244  const index_exprt &index_expr, functionst &out_functions)
245 {
246  expressionst potential_array_values;
247  bool array_const;
248  bool resolved=
249  try_resolve_index_of(index_expr, potential_array_values, array_const);
250 
251  if(!resolved)
252  {
253  LOG("Could not resolve array", index_expr);
254  return false;
255  }
256 
257  if(!array_const)
258  {
259  LOG("Array not const", index_expr);
260  return false;
261  }
262 
263  return try_resolve_function_calls(potential_array_values, out_functions);
264 }
265 
276  const member_exprt &member_expr, functionst &out_functions)
277 {
278  expressionst potential_component_values;
279  bool struct_const;
280  bool resolved=
281  try_resolve_member(member_expr, potential_component_values, struct_const);
282 
283  if(!resolved)
284  {
285  LOG("Could not resolve struct", member_expr);
286  return false;
287  }
288 
289  if(!struct_const)
290  {
291  LOG("Struct was not const so can't resolve values on it", member_expr);
292  return false;
293  }
294 
295  return try_resolve_function_calls(potential_component_values, out_functions);
296 }
297 
307  const address_of_exprt &address_expr, functionst &out_functions)
308 {
309  bool resolved=
310  try_resolve_function_call(address_expr.object(), out_functions);
311  if(!resolved)
312  {
313  LOG("Failed to resolve address of", address_expr);
314  }
315  return resolved;
316 }
317 
328  const dereference_exprt &deref_expr, functionst &out_functions)
329 {
330  expressionst potential_deref_values;
331  bool deref_const;
332  bool resolved=
333  try_resolve_dereference(deref_expr, potential_deref_values, deref_const);
334 
335  if(!resolved)
336  {
337  LOG("Failed to squash dereference", deref_expr);
338  return false;
339  }
340 
341  if(!deref_const)
342  {
343  LOG("Dereferenced value was not const so can't dereference", deref_expr);
344  return false;
345  }
346 
347  return try_resolve_function_calls(potential_deref_values, out_functions);
348 }
349 
360  const typecast_exprt &typecast_expr, functionst &out_functions)
361 {
362  // We simply ignore typecasts and assume they are valid
363  // I thought simplify_expr would deal with this, but for example
364  // a cast from a 32 bit width int to a 64bit width int it doesn't seem
365  // to allow
366  functionst typecast_values;
367  bool resolved=
368  try_resolve_function_call(typecast_expr.op(), typecast_values);
369 
370  if(resolved)
371  {
372  out_functions.insert(typecast_values.begin(), typecast_values.end());
373  return true;
374  }
375  else
376  {
377  LOG("Failed to squash typecast", typecast_expr);
378  return false;
379  }
380 }
381 
397  const exprt &expr, expressionst &out_resolved_expression, bool &out_is_const)
398 {
399  exprt simplified_expr=simplify_expr(expr, ns);
400  bool resolved;
401  expressionst resolved_expressions;
402  bool is_resolved_expression_const = false;
403  if(simplified_expr.id()==ID_index)
404  {
405  const index_exprt &index_expr=to_index_expr(simplified_expr);
406  resolved=
408  index_expr, resolved_expressions, is_resolved_expression_const);
409  }
410  else if(simplified_expr.id()==ID_member)
411  {
412  const member_exprt &member_expr=to_member_expr(simplified_expr);
413  resolved=try_resolve_member(
414  member_expr, resolved_expressions, is_resolved_expression_const);
415  }
416  else if(simplified_expr.id()==ID_dereference)
417  {
418  const dereference_exprt &deref=to_dereference_expr(simplified_expr);
419  resolved=
421  deref, resolved_expressions, is_resolved_expression_const);
422  }
423  else if(simplified_expr.id()==ID_typecast)
424  {
425  typecast_exprt typecast_expr=to_typecast_expr(simplified_expr);
426  resolved=
428  typecast_expr, resolved_expressions, is_resolved_expression_const);
429  }
430  else if(simplified_expr.id()==ID_symbol)
431  {
432  LOG("Non const symbol will not be squashed", simplified_expr);
433  resolved=false;
434  }
435  else
436  {
437  resolved_expressions.push_back(simplified_expr);
438  is_resolved_expression_const=is_const_expression(simplified_expr);
439  resolved=true;
440  }
441 
442  if(resolved)
443  {
444  out_resolved_expression.insert(
445  out_resolved_expression.end(),
446  resolved_expressions.begin(),
447  resolved_expressions.end());
448  out_is_const=is_resolved_expression_const;
449  return true;
450  }
451  else
452  {
453  return false;
454  }
455 }
456 
466  const exprt &expr, mp_integer &out_array_index)
467 {
468  expressionst index_value_expressions;
469  bool is_const=false;
470  bool resolved=try_resolve_expression(expr, index_value_expressions, is_const);
471  if(resolved)
472  {
473  if(index_value_expressions.size()==1 &&
474  index_value_expressions.front().id()==ID_constant)
475  {
476  const constant_exprt &constant_expr=
477  to_constant_expr(index_value_expressions.front());
478  mp_integer array_index;
479  bool errors=to_integer(constant_expr, array_index);
480  if(!errors)
481  {
482  out_array_index=array_index;
483  }
484  return !errors;
485  }
486  else
487  {
488  return false;
489  }
490  }
491  else
492  {
493  return false;
494  }
495 }
496 
508  const index_exprt &index_expr,
509  expressionst &out_expressions,
510  bool &out_is_const)
511 {
512  // Get the array(s) it belongs to
513  expressionst potential_array_exprs;
514  bool array_const=false;
515  bool resolved_array=
517  index_expr.array(),
518  potential_array_exprs,
519  array_const);
520 
521  if(resolved_array)
522  {
523  bool all_possible_const=true;
524  for(const exprt &potential_array_expr : potential_array_exprs)
525  {
526  all_possible_const=
527  all_possible_const &&
528  is_const_type(potential_array_expr.type().subtype());
529 
530  if(potential_array_expr.id()==ID_array)
531  {
532  // Get the index if we can
533  mp_integer value;
534  if(try_resolve_index_value(index_expr.index(), value))
535  {
536  expressionst array_out_functions;
537  const exprt &func_expr =
538  potential_array_expr.operands()[numeric_cast_v<std::size_t>(value)];
539  bool value_const=false;
540  bool resolved_value=
541  try_resolve_expression(func_expr, array_out_functions, value_const);
542 
543  if(resolved_value)
544  {
545  out_expressions.insert(
546  out_expressions.end(),
547  array_out_functions.begin(),
548  array_out_functions.end());
549  }
550  else
551  {
552  LOG("Failed to resolve array value", func_expr);
553  return false;
554  }
555  }
556  else
557  {
558  // We don't know what index it is,
559  // but we know the value is from the array
560  for(const exprt &array_entry : potential_array_expr.operands())
561  {
562  expressionst array_contents;
563  bool is_entry_const;
564  bool resolved_value=
566  array_entry, array_contents, is_entry_const);
567 
568  if(!resolved_value)
569  {
570  LOG("Failed to resolve array value", array_entry);
571  return false;
572  }
573 
574  for(const exprt &resolved_array_entry : array_contents)
575  {
576  out_expressions.push_back(resolved_array_entry);
577  }
578  }
579  }
580  }
581  else
582  {
583  LOG(
584  "Squashing index of did not result in an array",
585  potential_array_expr);
586  return false;
587  }
588  }
589 
590  out_is_const=all_possible_const || array_const;
591  return true;
592  }
593  else
594  {
595  LOG("Failed to squash index of to array expression", index_expr);
596  return false;
597  }
598 }
599 
609  const member_exprt &member_expr,
610  expressionst &out_expressions,
611  bool &out_is_const)
612 {
613  expressionst potential_structs;
614  bool is_struct_const;
615 
616  // Get the struct it belongs to
617  bool resolved_struct=
619  member_expr.compound(), potential_structs, is_struct_const);
620  if(resolved_struct)
621  {
622  for(const exprt &potential_struct : potential_structs)
623  {
624  if(potential_struct.id()==ID_struct)
625  {
626  struct_exprt struct_expr=to_struct_expr(potential_struct);
627  const exprt &component_value=
628  get_component_value(struct_expr, member_expr);
629  expressionst resolved_expressions;
630  bool component_const=false;
631  bool resolved=
633  component_value, resolved_expressions, component_const);
634  if(resolved)
635  {
636  out_expressions.insert(
637  out_expressions.end(),
638  resolved_expressions.begin(),
639  resolved_expressions.end());
640  }
641  else
642  {
643  LOG("Could not resolve component value", component_value);
644  return false;
645  }
646  }
647  else
648  {
649  LOG(
650  "Squashing member access did not resolve in a struct",
651  potential_struct);
652  return false;
653  }
654  }
655  out_is_const=is_struct_const;
656  return true;
657  }
658  else
659  {
660  LOG("Failed to squash struct access", member_expr);
661  return false;
662  }
663 }
664 
676  const dereference_exprt &deref_expr,
677  expressionst &out_expressions,
678  bool &out_is_const)
679 {
680  // We had a pointer, we need to check both the pointer
681  // type can't be changed, and what it what pointing to
682  // can't be changed
683  expressionst pointer_values;
684  bool pointer_const;
685  bool resolved=
686  try_resolve_expression(deref_expr.pointer(), pointer_values, pointer_const);
687  if(resolved && pointer_const)
688  {
689  bool all_objects_const=true;
690  for(const exprt &pointer_val : pointer_values)
691  {
692  if(pointer_val.id()==ID_address_of)
693  {
694  address_of_exprt address_expr=to_address_of_expr(pointer_val);
695  bool object_const=false;
696  expressionst out_object_values;
697  const bool resolved_address = try_resolve_expression(
698  address_expr.object(), out_object_values, object_const);
699 
700  if(resolved_address)
701  {
702  out_expressions.insert(
703  out_expressions.end(),
704  out_object_values.begin(),
705  out_object_values.end());
706 
707  all_objects_const&=object_const;
708  }
709  else
710  {
711  LOG("Failed to resolve value of a dereference", address_expr);
712  }
713  }
714  else
715  {
716  LOG(
717  "Squashing dereference did not result in an address", pointer_val);
718  return false;
719  }
720  }
721  out_is_const=all_objects_const;
722  return true;
723  }
724  else
725  {
726  if(!resolved)
727  {
728  LOG("Failed to resolve pointer of dereference", deref_expr);
729  }
730  else if(!pointer_const)
731  {
732  LOG("Pointer value not const so can't squash", deref_expr);
733  }
734  return false;
735  }
736 }
737 
746  const typecast_exprt &typecast_expr,
747  expressionst &out_expressions,
748  bool &out_is_const)
749 {
750  expressionst typecast_values;
751  bool typecast_const;
752  bool resolved=
754  typecast_expr.op(), typecast_values, typecast_const);
755 
756  if(resolved)
757  {
758  out_expressions.insert(
759  out_expressions.end(),
760  typecast_values.begin(),
761  typecast_values.end());
762  out_is_const=typecast_const;
763  return true;
764  }
765  else
766  {
767  LOG("Could not resolve typecast value", typecast_expr);
768  return false;
769  }
770 }
771 
776  const exprt &expression) const
777 {
778  return is_const_type(expression.type());
779 }
780 
786 {
787  if(type.id() == ID_array && type.subtype().get_bool(ID_C_constant))
788  return true;
789 
790  return type.get_bool(ID_C_constant);
791 }
792 
799  const struct_exprt &struct_expr, const member_exprt &member_expr)
800 {
801  const struct_typet &struct_type=to_struct_type(ns.follow(struct_expr.type()));
802  size_t component_number=
803  struct_type.component_number(member_expr.get_component_name());
804 
805  return struct_expr.operands()[component_number];
806 }
bool to_integer(const constant_exprt &expr, mp_integer &int_value)
Convert a constant expression expr to an arbitrary-precision integer.
Definition: arith_tools.cpp:19
Operator to return the address of an object.
Definition: pointer_expr.h:341
exprt & object()
Definition: pointer_expr.h:350
A constant literal expression.
Definition: std_expr.h:2753
Operator to dereference a pointer.
Definition: pointer_expr.h:628
Base class for all expressions.
Definition: expr.h:54
bool is_zero() const
Return whether the expression is a constant representing 0.
Definition: expr.cpp:64
typet & type()
Return the type of the expression.
Definition: expr.h:82
operandst & operands()
Definition: expr.h:92
Array index operator.
Definition: std_expr.h:1328
exprt & array()
Definition: std_expr.h:1344
exprt & index()
Definition: std_expr.h:1354
bool get_bool(const irep_namet &name) const
Definition: irep.cpp:58
const irep_idt & id() const
Definition: irep.h:407
Extract member of struct or union.
Definition: std_expr.h:2613
const exprt & compound() const
Definition: std_expr.h:2654
irep_idt get_component_name() const
Definition: std_expr.h:2627
const typet & follow(const typet &) const
Resolve type symbol to the type it points to.
Definition: namespace.cpp:49
A namespacet is essentially one or two symbol tables bound together, to allow for symbol lookups in t...
Definition: namespace.h:91
remove_const_function_pointerst(message_handlert &message_handler, const namespacet &ns, const symbol_tablet &symbol_table)
To take a function call on a function pointer, and if possible resolve it to a small collection of po...
bool try_resolve_function_call(const exprt &expr, functionst &out_functions)
To resolve an expression to the specific function calls it can be.
bool try_resolve_function_calls(const expressionst &exprs, functionst &out_functions)
To resolve a collection of expressions to the specific function calls they can be.
bool try_resolve_expression(const exprt &expr, expressionst &out_resolved_expression, bool &out_is_const)
To squash various expr types to simplify the expression.
exprt get_component_value(const struct_exprt &struct_expr, const member_exprt &member_expr)
To extract the value of the specific component within a struct.
bool try_resolve_typecast(const typecast_exprt &typecast_expr, expressionst &out_expressions, bool &out_is_const)
To squash a typecast access.
bool try_resolve_dereference_function_call(const dereference_exprt &deref_expr, functionst &out_functions)
To resolve an expression to the specific function calls it can be.
bool try_resolve_member(const member_exprt &member_expr, expressionst &out_expressions, bool &out_is_const)
To squash an member access by first finding the struct it is accessing Then return the squashed value...
bool is_const_type(const typet &type) const
To evaluate the const-ness of the type.
bool try_resolve_index_of_function_call(const index_exprt &index_expr, functionst &out_functions)
To resolve an expression to the specific function calls it can be.
bool try_resolve_index_value(const exprt &index_value_expr, mp_integer &out_array_index)
Given an index into an array, resolve, if possible, the index that is being accessed.
bool operator()(const exprt &base_expression, functionst &out_functions)
To take a function call on a function pointer, and if possible resolve it to a small collection of po...
bool is_const_expression(const exprt &expression) const
To evaluate the const-ness of the expression type.
std::unordered_set< symbol_exprt, irep_hash > functionst
bool try_resolve_address_of_function_call(const address_of_exprt &address_expr, functionst &out_functions)
To resolve an expression to the specific function calls it can be.
bool try_resolve_member_function_call(const member_exprt &member_expr, functionst &out_functions)
To resolve an expression to the specific function calls it can be.
exprt resolve_symbol(const symbol_exprt &symbol_expr) const
Look up a symbol in the symbol table and return its value.
bool try_resolve_index_of(const index_exprt &index_expr, expressionst &out_expressions, bool &out_is_const)
To squash an index access by first finding the array it is accessing Then if the index can be resolve...
bool try_resolve_dereference(const dereference_exprt &deref_expr, expressionst &out_expressions, bool &out_is_const)
To squash a dereference access by first finding the address_of the dereference is dereferencing.
bool try_resolve_typecast_function_call(const typecast_exprt &typecast_expr, functionst &out_functions)
To resolve an expression to the specific function calls it can be.
exprt replace_const_symbols(const exprt &expression) const
To collapse the symbols down to their values where possible This takes a very general approach,...
Struct constructor from list of elements.
Definition: std_expr.h:1668
Structure type, corresponds to C style structs.
Definition: std_types.h:231
std::size_t component_number(const irep_idt &component_name) const
Return the sequence number of the component with given name.
Definition: std_types.cpp:32
Expression to hold a symbol (variable)
Definition: std_expr.h:80
const irep_idt & get_identifier() const
Definition: std_expr.h:109
const symbolt & lookup_ref(const irep_idt &name) const
Find a symbol in the symbol table for read-only access.
The symbol table.
Definition: symbol_table.h:14
Symbol table entry.
Definition: symbol.h:28
typet type
Type of symbol.
Definition: symbol.h:31
exprt value
Initial value of symbol.
Definition: symbol.h:34
Semantic type conversion.
Definition: std_expr.h:1866
The type of an expression, extends irept.
Definition: type.h:28
const typet & subtype() const
Definition: type.h:47
const exprt & op() const
Definition: std_expr.h:293
API to expression classes for Pointers.
const dereference_exprt & to_dereference_expr(const exprt &expr)
Cast an exprt to a dereference_exprt.
Definition: pointer_expr.h:684
const address_of_exprt & to_address_of_expr(const exprt &expr)
Cast an exprt to an address_of_exprt.
Definition: pointer_expr.h:378
#define LOG(message, irep)
exprt simplify_expr(exprt src, const namespacet &ns)
BigInt mp_integer
Definition: smt_terms.h:12
#define PRECONDITION(CONDITION)
Definition: invariant.h:463
API to expression classes.
const constant_exprt & to_constant_expr(const exprt &expr)
Cast an exprt to a constant_exprt.
Definition: std_expr.h:2786
const symbol_exprt & to_symbol_expr(const exprt &expr)
Cast an exprt to a symbol_exprt.
Definition: std_expr.h:189
const typecast_exprt & to_typecast_expr(const exprt &expr)
Cast an exprt to a typecast_exprt.
Definition: std_expr.h:1900
const struct_exprt & to_struct_expr(const exprt &expr)
Cast an exprt to a struct_exprt.
Definition: std_expr.h:1691
const member_exprt & to_member_expr(const exprt &expr)
Cast an exprt to a member_exprt.
Definition: std_expr.h:2697
const index_exprt & to_index_expr(const exprt &expr)
Cast an exprt to an index_exprt.
Definition: std_expr.h:1382
const struct_typet & to_struct_type(const typet &type)
Cast a typet to a struct_typet.
Definition: std_types.h:308
Author: Diffblue Ltd.