CBMC
reaching_definitions.h
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Range-based reaching definitions analysis (following Field-
4  Sensitive Program Dependence Analysis, Litvak et al., FSE 2010)
5 
6 Author: Michael Tautschnig
7 
8 Date: February 2013
9 
10 \*******************************************************************/
11 
24 
25 #ifndef CPROVER_ANALYSES_REACHING_DEFINITIONS_H
26 #define CPROVER_ANALYSES_REACHING_DEFINITIONS_H
27 
28 #include <util/threeval.h>
29 
30 #include "ai.h"
31 #include "goto_rw.h"
32 
33 class value_setst;
34 class is_threadedt;
35 class dirtyt;
37 
41 template<typename V>
43 {
44 public:
45  const V &get(const std::size_t value_index) const
46  {
47  PRECONDITION(value_index < values.size());
48  return values[value_index]->first;
49  }
50 
51  std::size_t add(const V &value)
52  {
53  inner_mapt &m=value_map[value.identifier];
54 
55  std::pair<typename inner_mapt::iterator, bool> entry=
56  m.insert(std::make_pair(value, values.size()));
57 
58  if(entry.second)
59  values.push_back(entry.first);
60 
61  return entry.first->second;
62  }
63 
64  void clear()
65  {
66  value_map.clear();
67  values.clear();
68  }
69 
70 protected:
71  typedef typename std::map<V, std::size_t> inner_mapt;
76  std::vector<typename inner_mapt::const_iterator> values;
80  std::unordered_map<irep_idt, inner_mapt> value_map;
81 };
82 
86 {
97 
99  const irep_idt &identifier,
101  const range_spect &bit_begin,
102  const range_spect &bit_end)
107  {
108  }
109 };
110 
113 inline bool operator<(
114  const reaching_definitiont &a,
115  const reaching_definitiont &b)
116 {
118  return true;
120  return false;
121 
123  return a.bit_begin.is_unknown();
124 
125  if(!a.bit_begin.is_unknown())
126  {
127  if(a.bit_begin < b.bit_begin)
128  return true;
129  if(b.bit_begin < a.bit_begin)
130  return false;
131  }
132 
133  if(a.bit_end.is_unknown() != b.bit_end.is_unknown())
134  return a.bit_end.is_unknown();
135 
136  if(!a.bit_end.is_unknown())
137  {
138  if(a.bit_end < b.bit_end)
139  return true;
140  if(b.bit_end < a.bit_end)
141  return false;
142  }
143 
144  // we do not expect comparison of unrelated definitions
145  // as this operator< is only used in sparse_bitvector_analysist
146  INVARIANT(
147  a.identifier == b.identifier, "comparison of unrelated definitions");
148 
149  return false;
150 }
151 
159 {
160 public:
164  : ai_domain_baset(),
165  has_values(false),
166  bv_container(_bv_container),
168  {
169  PRECONDITION(bv_container != nullptr);
170  }
171 
184  void transform(
185  const irep_idt &function_from,
186  trace_ptrt trace_from,
187  const irep_idt &function_to,
188  trace_ptrt trace_to,
189  ai_baset &ai,
190  const namespacet &ns) final override;
191 
192  void output(
193  std::ostream &out,
194  const ai_baset &,
195  const namespacet &) const final override
196  {
197  output(out);
198  }
199 
200  void make_top() final override
201  {
202  values.clear();
203  if(bv_container)
204  bv_container->clear();
205  has_values=tvt(true);
206  }
207 
208  void make_bottom() final override
209  {
210  values.clear();
211  if(bv_container)
212  bv_container->clear();
213  has_values=tvt(false);
214  }
215 
216  bool is_top() const override final
217  {
218  DATA_INVARIANT(!has_values.is_true() || values.empty(),
219  "If domain is top, the value map must be empty");
220  return has_values.is_true();
221  }
222 
223  bool is_bottom() const override final
224  {
226  "If domain is bottom, the value map must be empty");
227  return has_values.is_false();
228  }
229 
242  bool merge(const rd_range_domaint &other, trace_ptrt from, trace_ptrt to);
243 
244  bool merge_shared(
245  const rd_range_domaint &other,
246  locationt from,
247  locationt to,
248  const namespacet &ns);
249 
250  // each element x represents a range of bits [x.first, x.second)
251  typedef std::multimap<range_spect, range_spect> rangest;
252  typedef std::map<locationt, rangest, goto_programt::target_less_than>
254 
255  const ranges_at_loct &get(const irep_idt &identifier) const;
256  void clear_cache(const irep_idt &identifier) const
257  {
258  export_cache[identifier].clear();
259  }
260 
261 private:
266 
275 
276  typedef std::set<std::size_t> values_innert;
277  typedef std::map<irep_idt, values_innert> valuest;
284 
285  typedef std::map<irep_idt, ranges_at_loct> export_cachet;
298 
299  void populate_cache(const irep_idt &identifier) const;
300 
301  void transform_dead(
302  const namespacet &ns,
303  locationt from);
305  const namespacet &ns,
308  const namespacet &ns,
309  const irep_idt &function_from,
310  locationt from,
311  const irep_idt &function_to,
314  const namespacet &ns,
315  const irep_idt &function_from,
316  locationt from,
317  const irep_idt &function_to,
318  locationt to,
320  void transform_assign(
321  const namespacet &ns,
322  locationt from,
323  const irep_idt &function_to,
324  locationt to,
326 
327  void kill(
328  const irep_idt &identifier,
329  const range_spect &range_start,
330  const range_spect &range_end);
331  void kill_inf(
332  const irep_idt &identifier,
333  const range_spect &range_start);
334  bool gen(
335  locationt from,
336  const irep_idt &identifier,
337  const range_spect &range_start,
338  const range_spect &range_end);
339 
340  void output(std::ostream &out) const;
341 
342  bool merge_inner(
343  values_innert &dest,
344  const values_innert &other);
345 
347 };
348 
350  public concurrency_aware_ait<rd_range_domaint>,
351  public sparse_bitvector_analysist<reaching_definitiont>
352 {
353 public:
354  // constructor
356 
358 
359  void initialize(const goto_functionst &goto_functions) override;
360 
362  {
364  return *value_sets;
365  }
366 
368  {
370  return *is_threaded;
371  }
372 
373  const dirtyt &get_is_dirty() const
374  {
376  return *is_dirty;
377  }
378 
379 protected:
380  const namespacet &ns;
381  std::unique_ptr<value_setst> value_sets;
382  std::unique_ptr<is_threadedt> is_threaded;
383  std::unique_ptr<dirtyt> is_dirty;
384 };
385 
386 #endif // CPROVER_ANALYSES_REACHING_DEFINITIONS_H
Abstract Interpretation.
This is the basic interface of the abstract interpreter with default implementations of the core func...
Definition: ai.h:117
The interface offered by a domain, allows code to manipulate domains without knowing their exact type...
Definition: ai_domain.h:54
ai_history_baset::trace_ptrt trace_ptrt
Definition: ai_domain.h:73
goto_programt::const_targett locationt
Definition: ai_domain.h:72
Base class for concurrency-aware abstract interpretation.
Definition: ai.h:651
Dirty variables are ones which have their address taken so we can't reliably work out where they may ...
Definition: dirty.h:28
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:38
A collection of goto functions.
A namespacet is essentially one or two symbol tables bound together, to allow for symbol lookups in t...
Definition: namespace.h:94
Data type to describe upper and lower bounds of the range of bits that a read or write access may aff...
Definition: goto_rw.h:61
bool is_unknown() const
Definition: goto_rw.h:74
Because the class is inherited from ai_domain_baset, its instance represents an element of a domain o...
std::map< irep_idt, ranges_at_loct > export_cachet
void populate_cache(const irep_idt &identifier) const
Given the passed variable name identifier it collects data from bv_container for each ID in values[id...
export_cachet export_cache
It is a helper data structure.
void output(std::ostream &out, const ai_baset &, const namespacet &) const final override
void make_top() final override
all states – the analysis doesn't use this directly (see make_entry) and domains may refuse to implem...
void kill_inf(const irep_idt &identifier, const range_spect &range_start)
void transform_dead(const namespacet &ns, locationt from)
Computes an instance obtained from a *this by transformation over DEAD v GOTO instruction.
void transform_start_thread(const namespacet &ns, reaching_definitions_analysist &rd)
bool is_top() const override final
const ranges_at_loct & get(const irep_idt &identifier) const
void clear_cache(const irep_idt &identifier) const
bool is_bottom() const override final
sparse_bitvector_analysist< reaching_definitiont > *const bv_container
It points to the actual reaching definitions data of individual program variables.
void transform_function_call(const namespacet &ns, const irep_idt &function_from, locationt from, const irep_idt &function_to, reaching_definitions_analysist &rd)
rd_range_domaint(sparse_bitvector_analysist< reaching_definitiont > *_bv_container, message_handlert &message_handler)
bool merge(const rd_range_domaint &other, trace_ptrt from, trace_ptrt to)
Implements the "join" operation of two instances *this and other.
void transform_end_function(const namespacet &ns, const irep_idt &function_from, locationt from, const irep_idt &function_to, locationt to, reaching_definitions_analysist &rd)
void make_bottom() final override
no states
void transform_assign(const namespacet &ns, locationt from, const irep_idt &function_to, locationt to, reaching_definitions_analysist &rd)
bool merge_inner(values_innert &dest, const values_innert &other)
std::multimap< range_spect, range_spect > rangest
bool gen(locationt from, const irep_idt &identifier, const range_spect &range_start, const range_spect &range_end)
A utility function which updates internal data structures by inserting a new reaching definition reco...
void kill(const irep_idt &identifier, const range_spect &range_start, const range_spect &range_end)
std::map< locationt, rangest, goto_programt::target_less_than > ranges_at_loct
tvt has_values
This (three value logic) flag determines, whether the instance represents top, bottom,...
void transform(const irep_idt &function_from, trace_ptrt trace_from, const irep_idt &function_to, trace_ptrt trace_to, ai_baset &ai, const namespacet &ns) final override
Computes an instance obtained from the instance *this by transformation over a GOTO instruction refer...
std::map< irep_idt, values_innert > valuest
valuest values
It is an ordered map from program variable names to IDs of reaching_definitiont instances stored in m...
bool merge_shared(const rd_range_domaint &other, locationt from, locationt to, const namespacet &ns)
std::set< std::size_t > values_innert
message_handlert & message_handler
const is_threadedt & get_is_threaded() const
std::unique_ptr< is_threadedt > is_threaded
std::unique_ptr< dirtyt > is_dirty
std::unique_ptr< value_setst > value_sets
value_setst & get_value_sets() const
reaching_definitions_analysist(const namespacet &_ns, message_handlert &)
const dirtyt & get_is_dirty() const
void initialize(const goto_functionst &goto_functions) override
Initialize all the abstract states for a whole program.
An instance of this class provides an assignment of unique numeric ID to each inserted reaching_defin...
std::map< V, std::size_t > inner_mapt
const V & get(const std::size_t value_index) const
std::vector< typename inner_mapt::const_iterator > values
It is a map from an ID to the corresponding reaching_definitiont instance inside the map value_map.
std::unordered_map< irep_idt, inner_mapt > value_map
A map from names of program variables to a set of pairs (reaching_definitiont, ID).
std::size_t add(const V &value)
Definition: threeval.h:20
bool is_false() const
Definition: threeval.h:26
bool is_true() const
Definition: threeval.h:25
bool operator<(const reaching_definitiont &a, const reaching_definitiont &b)
In order to use instances of this structure as keys in ordered containers, such as std::map,...
#define DATA_INVARIANT(CONDITION, REASON)
This condition should be used to document that assumptions that are made on goto_functions,...
Definition: invariant.h:534
#define PRECONDITION(CONDITION)
Definition: invariant.h:463
#define INVARIANT(CONDITION, REASON)
This macro uses the wrapper function 'invariant_violated_string'.
Definition: invariant.h:423
A total order over targett and const_targett.
Definition: goto_program.h:392
Identifies a GOTO instruction where a given variable is defined (i.e.
range_spect bit_begin
The two integers below define a range of bits (i.e.
ai_domain_baset::locationt definition_at
The iterator to the GOTO instruction where the variable has been written to.
reaching_definitiont(const irep_idt &identifier, const ai_domain_baset::locationt &definition_at, const range_spect &bit_begin, const range_spect &bit_end)
irep_idt identifier
The name of the variable which was defined.