CBMC
dfcc_infer_loop_assigns.cpp
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Dynamic frame condition checking
4 
5 Author: Remi Delmas, delmasrd@amazon.com
6 
7 \*******************************************************************/
9 
10 #include <util/expr.h>
11 #include <util/find_symbols.h>
12 #include <util/message.h>
13 #include <util/pointer_expr.h>
14 #include <util/std_code.h>
15 
17 
18 #include <analyses/goto_rw.h>
21 
23 #include "dfcc_root_object.h"
24 
26 static exprt
28 {
29  const symbolt &object_whole_sym = ns.lookup(CPROVER_PREFIX "object_whole");
30  const code_typet &object_whole_code_type =
31  to_code_type(object_whole_sym.type);
33  object_whole_sym.symbol_expr(),
34  {{expr}},
35  object_whole_code_type.return_type(),
36  expr.source_location());
37 }
38 
41 static bool
42 depends_on(const exprt &expr, std::unordered_set<irep_idt> identifiers)
43 {
44  const std::unordered_set<irep_idt> ids = find_symbol_identifiers(expr);
45  for(const auto &id : ids)
46  {
47  if(identifiers.find(id) != identifiers.end())
48  return true;
49  }
50  return false;
51 }
52 
58 std::unordered_set<irep_idt> gen_loop_locals_set(
59  const irep_idt &function_id,
60  goto_functiont &goto_function,
61  const dfcc_loop_nesting_graph_nodet &loop_node,
62  message_handlert &message_handler,
63  const namespacet &ns)
64 {
65  std::unordered_set<irep_idt> loop_locals;
66  std::unordered_set<irep_idt> non_loop_locals;
67 
68  const auto &loop = loop_node.instructions;
69 
70  // All identifiers declared outside the loop.
71  std::unordered_set<irep_idt> non_loop_decls;
72  // Ranges of all read/write outside the loop.
73  rw_range_sett non_loop_rw_range_set(ns, message_handler);
74 
75  Forall_goto_program_instructions(i_it, goto_function.body)
76  {
77  // All variables declared in loops are loop locals.
78  if(i_it->is_decl() && loop.contains(i_it))
79  {
80  loop_locals.insert(i_it->decl_symbol().get_identifier());
81  }
82  // Record all other declared variables and their ranges.
83  else if(i_it->is_decl())
84  {
85  non_loop_decls.insert(i_it->decl_symbol().get_identifier());
86  }
87  // Record all writing/reading outside the loop.
88  else if(
89  (i_it->is_assign() || i_it->is_function_call()) && !loop.contains(i_it))
90  {
91  goto_rw(function_id, i_it, non_loop_rw_range_set);
92  }
93  }
94 
95  // Check if declared variables are loop locals.
96  for(const auto &decl_id : non_loop_decls)
97  {
98  bool is_loop_local = true;
99  // No write to the declared variable.
100  for(const auto &writing_rw : non_loop_rw_range_set.get_w_set())
101  {
102  if(decl_id == writing_rw.first)
103  {
104  is_loop_local = false;
105  break;
106  }
107  }
108 
109  // No read to the declared variable.
110  for(const auto &writing_rw : non_loop_rw_range_set.get_r_set())
111  {
112  if(decl_id == writing_rw.first)
113  {
114  is_loop_local = false;
115  break;
116  }
117  }
118 
119  const auto latch_target = loop_node.latch;
120 
121  // Loop locals are not used in loop contracts.
122  for(const auto &id :
124  {
125  if(decl_id == id)
126  {
127  is_loop_local = false;
128  break;
129  }
130  }
131 
132  for(const auto &id :
133  find_symbol_identifiers(get_loop_invariants(latch_target, false)))
134  {
135  if(decl_id == id)
136  {
137  is_loop_local = false;
138  break;
139  }
140  }
141 
142  for(const auto &id :
143  find_symbol_identifiers(get_loop_decreases(latch_target, false)))
144  {
145  if(decl_id == id)
146  {
147  is_loop_local = false;
148  break;
149  }
150  }
151 
152  // Collect all loop locals.
153  if(is_loop_local)
154  loop_locals.insert(decl_id);
155  }
156 
157  return loop_locals;
158 }
159 
161 static std::unordered_set<irep_idt>
163 {
164  std::unordered_set<irep_idt> identifiers;
165  for(const auto &instruction : src.instructions)
166  {
167  // compute forward edges first
168  switch(instruction.type())
169  {
170  case ASSERT:
171  case ASSUME:
172  case GOTO:
173  find_symbols(instruction.condition(), identifiers);
174  break;
175 
176  case FUNCTION_CALL:
177  find_symbols(instruction.call_lhs(), identifiers);
178  for(const auto &e : instruction.call_arguments())
179  find_symbols(e, identifiers);
180  break;
181  case ASSIGN:
182  case OTHER:
183 
184  case SET_RETURN_VALUE:
185  case DECL:
186  case DEAD:
187  for(const auto &e : instruction.code().operands())
188  {
189  find_symbols(e, identifiers);
190  }
191  break;
192 
193  case END_THREAD:
194  case END_FUNCTION:
195  case ATOMIC_BEGIN:
196  case ATOMIC_END:
197  case SKIP:
198  case LOCATION:
199  case CATCH:
200  case THROW:
201  case START_THREAD:
202  break;
203  case NO_INSTRUCTION_TYPE:
204  case INCOMPLETE_GOTO:
205  UNREACHABLE;
206  break;
207  }
208  }
209  return identifiers;
210 }
211 
217  const local_may_aliast &local_may_alias,
218  goto_functiont &goto_function,
219  const dfcc_loop_nesting_graph_nodet &loop,
220  const std::unordered_set<irep_idt> &candidate_targets,
221  message_handlert &message_handler,
222  const namespacet &ns)
223 {
224  // infer
225  assignst assigns;
226  infer_loop_assigns(local_may_alias, loop.instructions, assigns);
227 
228  // compute locals
229  std::unordered_set<irep_idt> loop_locals =
230  gen_loop_locals_set(irep_idt(), goto_function, loop, message_handler, ns);
231 
232  // widen or drop targets that depend on loop-locals or are non-constant,
233  // ie. depend on other locations assigned by the loop.
234  // e.g: if the loop assigns {i, a[i]}, then a[i] is non-constant.
236  assignst result;
237  for(const auto &expr : assigns)
238  {
239  // Skip targets that only depend on non-visible identifiers.
240  if(!depends_on(expr, candidate_targets))
241  {
242  continue;
243  }
244 
245  if(depends_on(expr, loop_locals))
246  {
247  // Target depends on loop locals, attempt widening to the root object
248  auto root_objects = dfcc_root_objects(expr);
249  for(const auto &root_object : root_objects)
250  {
251  if(!depends_on(root_object, loop_locals))
252  {
253  address_of_exprt address_of_root_object(root_object);
254  address_of_root_object.add_source_location() =
255  root_object.source_location();
256  result.emplace(
257  make_object_whole_call_expr(address_of_root_object, ns));
258  }
259  }
260  }
261  else
262  {
263  address_of_exprt address_of_expr(expr);
264  address_of_expr.add_source_location() = expr.source_location();
265  // Widen assigns targets to object_whole if `expr` is a dereference or
266  // with constant address.
267  if(expr.id() == ID_dereference || !is_constant(address_of_expr))
268  {
269  // Target address is not constant, widening to the whole object
270  result.emplace(make_object_whole_call_expr(address_of_expr, ns));
271  }
272  else
273  {
274  result.emplace(expr);
275  }
276  }
277  }
278 
279  return result;
280 }
281 
285 {
286  Forall_goto_program_instructions(i_it, goto_function.body)
287  {
288  if(i_it->is_assign())
289  {
290  auto &lhs = i_it->assign_lhs();
291 
292  if(
293  lhs.id() == ID_symbol &&
294  to_symbol_expr(lhs).get_identifier() == CPROVER_PREFIX "dead_object")
295  {
296  i_it->turn_into_skip();
297  }
298  }
299  }
300 }
301 
303  std::map<std::size_t, assignst> &inferred_loop_assigns_map,
304  goto_functionst &goto_functions,
305  const goto_functiont &goto_function,
306  message_handlert &message_handler,
307  const namespacet &ns)
308 {
309  messaget log(message_handler);
310 
311  // Collect all candidate targets---identifiers visible in `goto_function`.
312  const auto candidate_targets = find_symbol_identifiers(goto_function.body);
313 
314  // We infer loop assigns based on the copy of `goto_function`.
315  goto_functiont goto_function_copy;
316  goto_function_copy.copy_from(goto_function);
317 
318  // Build the loop id map before inlining attempt. So that we can later
319  // distinguish loops in the original body and loops added by inlining.
320  const auto loop_nesting_graph =
321  build_loop_nesting_graph(goto_function_copy.body);
322  auto topsorted = loop_nesting_graph.topsort();
323  // skip function without loop.
324  if(topsorted.empty())
325  return;
326 
327  // Map from targett in `goto_function_copy` to loop number.
328  std::
329  unordered_map<goto_programt::const_targett, std::size_t, const_target_hash>
330  loop_number_map;
331 
332  for(const auto id : topsorted)
333  {
334  loop_number_map.emplace(
335  loop_nesting_graph[id].head, loop_nesting_graph[id].latch->loop_number);
336  }
337 
338  // We avoid inlining `malloc` and `free` whose variables are not assigns.
339  auto malloc_body = goto_functions.function_map.extract(irep_idt("malloc"));
340  auto free_body = goto_functions.function_map.extract(irep_idt("free"));
341 
342  // Inline all function calls in goto_function_copy.
344  goto_functions, goto_function_copy.body, ns, log.get_message_handler());
345  // Update the body to make sure all goto correctly jump to valid targets.
346  goto_function_copy.body.update();
347  // Build the loop graph after inlining.
348  const auto inlined_loop_nesting_graph =
349  build_loop_nesting_graph(goto_function_copy.body);
350 
351  // Alias analysis.
352  remove_dead_object_assignment(goto_function_copy);
353  local_may_aliast local_may_alias(goto_function_copy);
354 
355  auto inlined_topsorted = inlined_loop_nesting_graph.topsort();
356 
357  for(const auto inlined_id : inlined_topsorted)
358  {
359  // We only infer loop assigns for loops in the original function.
360  if(
361  loop_number_map.find(inlined_loop_nesting_graph[inlined_id].head) !=
362  loop_number_map.end())
363  {
364  const auto loop_number =
365  loop_number_map[inlined_loop_nesting_graph[inlined_id].head];
366  const auto inlined_loop = inlined_loop_nesting_graph[inlined_id];
367 
368  inferred_loop_assigns_map[loop_number] = dfcc_infer_loop_assigns_for_loop(
369  local_may_alias,
370  goto_function_copy,
371  inlined_loop,
372  candidate_targets,
373  message_handler,
374  ns);
375  }
376  }
377  // Restore the function boyd of `malloc` and `free`.
378  goto_functions.function_map.insert(std::move(malloc_body));
379  goto_functions.function_map.insert(std::move(free_body));
380 }
Operator to return the address of an object.
Definition: pointer_expr.h:540
Base type of functions.
Definition: std_types.h:583
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:38
Base class for all expressions.
Definition: expr.h:56
source_locationt & add_source_location()
Definition: expr.h:236
const source_locationt & source_location() const
Definition: expr.h:231
A collection of goto functions.
function_mapt function_map
A goto function, consisting of function body (see body) and parameter identifiers (see parameter_iden...
Definition: goto_function.h:24
goto_programt body
Definition: goto_function.h:26
void copy_from(const goto_functiont &other)
Definition: goto_function.h:76
A generic container class for the GOTO intermediate representation of one function.
Definition: goto_program.h:73
instructionst instructions
The list of instructions in the goto program.
Definition: goto_program.h:622
void update()
Update all indices.
A class containing utility functions for havocing expressions.
Definition: havoc_utils.h:28
Class that provides messages with a built-in verbosity 'level'.
Definition: message.h:154
A namespacet is essentially one or two symbol tables bound together, to allow for symbol lookups in t...
Definition: namespace.h:94
bool lookup(const irep_idt &name, const symbolt *&symbol) const override
See documentation for namespace_baset::lookup().
Definition: namespace.cpp:148
const objectst & get_r_set() const
Definition: goto_rw.h:215
const objectst & get_w_set() const
Definition: goto_rw.h:220
A side_effect_exprt representation of a function call side effect.
Definition: std_code.h:1692
Symbol table entry.
Definition: symbol.h:28
class symbol_exprt symbol_expr() const
Produces a symbol_exprt for a symbol.
Definition: symbol.cpp:121
typet type
Type of symbol.
Definition: symbol.h:31
#define CPROVER_PREFIX
static assignst dfcc_infer_loop_assigns_for_loop(const local_may_aliast &local_may_alias, goto_functiont &goto_function, const dfcc_loop_nesting_graph_nodet &loop, const std::unordered_set< irep_idt > &candidate_targets, message_handlert &message_handler, const namespacet &ns)
Infer loop assigns in the given loop.
static exprt make_object_whole_call_expr(const exprt &expr, const namespacet &ns)
Builds a call expression object_whole(expr)
static void remove_dead_object_assignment(goto_functiont &goto_function)
Remove assignments to __CPROVER_dead_object to avoid aliasing all targets that are assigned to __CPRO...
std::unordered_set< irep_idt > gen_loop_locals_set(const irep_idt &function_id, goto_functiont &goto_function, const dfcc_loop_nesting_graph_nodet &loop_node, message_handlert &message_handler, const namespacet &ns)
Collect identifiers that are local to this loop.
void dfcc_infer_loop_assigns_for_function(std::map< std::size_t, assignst > &inferred_loop_assigns_map, goto_functionst &goto_functions, const goto_functiont &goto_function, message_handlert &message_handler, const namespacet &ns)
Infer assigns clause targets for loops in goto_function from their instructions and an alias analysis...
static std::unordered_set< irep_idt > find_symbol_identifiers(const goto_programt &src)
Find all identifiers in src.
static bool depends_on(const exprt &expr, std::unordered_set< irep_idt > identifiers)
Returns true iff expr contains at least one identifier found in identifiers.
Infer a set of assigns clause targets for a natural loop.
dfcc_loop_nesting_grapht build_loop_nesting_graph(goto_programt &goto_program)
Builds a graph instance describing the nesting structure of natural loops in the given goto_program.
Builds a graph describing how loops are nested in a GOTO program.
std::unordered_set< exprt, irep_hash > dfcc_root_objects(const exprt &expr)
Computes a set of root object expressions from an lvalue or assigns clause target expression.
Utility functions that compute root object expressions for assigns clause targets and LHS expressions...
static bool find_symbols(symbol_kindt, const typet &, std::function< bool(const symbol_exprt &)>, std::unordered_set< irep_idt > &bindings, const std::vector< irep_idt > &subs_to_find)
Find identifiers with id ID_symbol of the sub expressions and the subs with ID in subs_to_find consid...
void goto_program_inline(goto_functionst &goto_functions, goto_programt &goto_program, const namespacet &ns, message_handlert &message_handler, bool adjust_function, bool caching)
Transitively inline all function calls found in a particular program.
Function Inlining This gives a number of different interfaces to the function inlining functionality ...
#define Forall_goto_program_instructions(it, program)
@ FUNCTION_CALL
Definition: goto_program.h:49
@ ATOMIC_END
Definition: goto_program.h:44
@ DEAD
Definition: goto_program.h:48
@ LOCATION
Definition: goto_program.h:41
@ END_FUNCTION
Definition: goto_program.h:42
@ ASSIGN
Definition: goto_program.h:46
@ ASSERT
Definition: goto_program.h:36
@ SET_RETURN_VALUE
Definition: goto_program.h:45
@ ATOMIC_BEGIN
Definition: goto_program.h:43
@ CATCH
Definition: goto_program.h:51
@ END_THREAD
Definition: goto_program.h:40
@ SKIP
Definition: goto_program.h:38
@ NO_INSTRUCTION_TYPE
Definition: goto_program.h:33
@ START_THREAD
Definition: goto_program.h:39
@ THROW
Definition: goto_program.h:50
@ DECL
Definition: goto_program.h:47
@ OTHER
Definition: goto_program.h:37
@ GOTO
Definition: goto_program.h:34
@ INCOMPLETE_GOTO
Definition: goto_program.h:52
@ ASSUME
Definition: goto_program.h:35
static void goto_rw(const irep_idt &function, goto_programt::const_targett target, const exprt &lhs, const exprt &function_expr, const exprt::operandst &arguments, rw_range_sett &rw_set)
Definition: goto_rw.cpp:845
Utilities for building havoc code for expressions.
std::set< exprt > assignst
Definition: havoc_utils.h:22
double log(double x)
Definition: math.c:2776
API to expression classes for Pointers.
#define UNREACHABLE
This should be used to mark dead code.
Definition: invariant.h:525
const symbol_exprt & to_symbol_expr(const exprt &expr)
Cast an exprt to a symbol_exprt.
Definition: std_expr.h:272
const code_typet & to_code_type(const typet &type)
Cast a typet to a code_typet.
Definition: std_types.h:788
bool is_constant(const typet &type)
This method tests, if the given typet is a constant.
Definition: std_types.h:29
A graph node that stores information about a natural loop.
loop_templatet< goto_programt::targett, goto_programt::target_less_than > instructions
Set of loop instructions.
goto_programt::targett latch
Loop latch instruction.
void infer_loop_assigns(const local_may_aliast &local_may_alias, const loopt &loop, assignst &assigns)
Infer loop assigns using alias analysis result local_may_alias.
Definition: utils.cpp:344
exprt get_loop_assigns(const goto_programt::const_targett &loop_end)
Extract loop assigns from annotated loop end.
Definition: utils.cpp:683
exprt get_loop_invariants(const goto_programt::const_targett &loop_end, const bool check_side_effect)
Extract loop invariants from annotated loop end.
Definition: utils.cpp:666
exprt get_loop_decreases(const goto_programt::const_targett &loop_end, const bool check_side_effect)
Extract loop decreases from annotated loop end.
Definition: utils.cpp:688
dstringt irep_idt