25 #ifndef CPROVER_ANALYSES_REACHING_DEFINITIONS_H
26 #define CPROVER_ANALYSES_REACHING_DEFINITIONS_H
45 const V &
get(
const std::size_t value_index)
const
48 return values[value_index]->first;
51 std::size_t
add(
const V &value)
55 std::pair<typename inner_mapt::iterator, bool> entry=
56 m.insert(std::make_pair(value,
values.size()));
59 values.push_back(entry.first);
61 return entry.first->second;
76 std::vector<typename inner_mapt::const_iterator>
values;
219 "If domain is top, the value map must be empty");
226 "If domain is bottom, the value map must be empty");
251 typedef std::multimap<range_spect, range_spect>
rangest;
252 typedef std::map<locationt, rangest, goto_programt::target_less_than>
277 typedef std::map<irep_idt, values_innert>
valuest;
340 void output(std::ostream &out)
const;
This is the basic interface of the abstract interpreter with default implementations of the core func...
The interface offered by a domain, allows code to manipulate domains without knowing their exact type...
ai_history_baset::trace_ptrt trace_ptrt
goto_programt::const_targett locationt
Base class for concurrency-aware abstract interpretation.
Dirty variables are ones which have their address taken so we can't reliably work out where they may ...
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
A collection of goto functions.
A namespacet is essentially one or two symbol tables bound together, to allow for symbol lookups in t...
Data type to describe upper and lower bounds of the range of bits that a read or write access may aff...
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
virtual ~reaching_definitions_analysist()
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)
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,...
#define PRECONDITION(CONDITION)
#define INVARIANT(CONDITION, REASON)
This macro uses the wrapper function 'invariant_violated_string'.
A total order over targett and const_targett.
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.