35 object_whole_code_type.return_type(),
45 for(
const auto &
id : ids)
47 if(identifiers.find(
id) != identifiers.end())
65 std::unordered_set<irep_idt> loop_locals;
66 std::unordered_set<irep_idt> non_loop_locals;
71 std::unordered_set<irep_idt> non_loop_decls;
78 if(i_it->is_decl() && loop.contains(i_it))
80 loop_locals.insert(i_it->decl_symbol().get_identifier());
83 else if(i_it->is_decl())
85 non_loop_decls.insert(i_it->decl_symbol().get_identifier());
89 (i_it->is_assign() || i_it->is_function_call()) && !loop.contains(i_it))
91 goto_rw(function_id, i_it, non_loop_rw_range_set);
96 for(
const auto &decl_id : non_loop_decls)
98 bool is_loop_local =
true;
100 for(
const auto &writing_rw : non_loop_rw_range_set.
get_w_set())
102 if(decl_id == writing_rw.first)
104 is_loop_local =
false;
110 for(
const auto &writing_rw : non_loop_rw_range_set.
get_r_set())
112 if(decl_id == writing_rw.first)
114 is_loop_local =
false;
119 const auto latch_target = loop_node.
latch;
127 is_loop_local =
false;
137 is_loop_local =
false;
147 is_loop_local =
false;
154 loop_locals.insert(decl_id);
161 static std::unordered_set<irep_idt>
164 std::unordered_set<irep_idt> identifiers;
168 switch(instruction.type())
178 for(
const auto &e : instruction.call_arguments())
187 for(
const auto &e : instruction.code().operands())
220 const std::unordered_set<irep_idt> &candidate_targets,
229 std::unordered_set<irep_idt> loop_locals =
237 for(
const auto &expr : assigns)
249 for(
const auto &root_object : root_objects)
255 root_object.source_location();
267 if(expr.id() == ID_dereference || !
is_constant(address_of_expr))
274 result.emplace(expr);
288 if(i_it->is_assign())
290 auto &lhs = i_it->assign_lhs();
293 lhs.id() == ID_symbol &&
296 i_it->turn_into_skip();
303 std::map<std::size_t, assignst> &inferred_loop_assigns_map,
316 goto_function_copy.
copy_from(goto_function);
320 const auto loop_nesting_graph =
322 auto topsorted = loop_nesting_graph.topsort();
324 if(topsorted.empty())
329 unordered_map<goto_programt::const_targett, std::size_t, const_target_hash>
332 for(
const auto id : topsorted)
334 loop_number_map.emplace(
335 loop_nesting_graph[
id].head, loop_nesting_graph[
id].latch->loop_number);
344 goto_functions, goto_function_copy.
body, ns,
log.get_message_handler());
348 const auto inlined_loop_nesting_graph =
355 auto inlined_topsorted = inlined_loop_nesting_graph.topsort();
357 for(
const auto inlined_id : inlined_topsorted)
361 loop_number_map.find(inlined_loop_nesting_graph[inlined_id].head) !=
362 loop_number_map.end())
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];
378 goto_functions.
function_map.insert(std::move(malloc_body));
379 goto_functions.
function_map.insert(std::move(free_body));
Operator to return the address of an object.
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Base class for all expressions.
source_locationt & add_source_location()
const source_locationt & source_location() const
A collection of goto functions.
function_mapt function_map
A goto function, consisting of function body (see body) and parameter identifiers (see parameter_iden...
void copy_from(const goto_functiont &other)
A generic container class for the GOTO intermediate representation of one function.
instructionst instructions
The list of instructions in the goto program.
void update()
Update all indices.
A class containing utility functions for havocing expressions.
Class that provides messages with a built-in verbosity 'level'.
A namespacet is essentially one or two symbol tables bound together, to allow for symbol lookups in t...
bool lookup(const irep_idt &name, const symbolt *&symbol) const override
See documentation for namespace_baset::lookup().
const objectst & get_r_set() const
const objectst & get_w_set() const
A side_effect_exprt representation of a function call side effect.
class symbol_exprt symbol_expr() const
Produces a symbol_exprt for a symbol.
typet type
Type of symbol.
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)
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)
Utilities for building havoc code for expressions.
std::set< exprt > assignst
API to expression classes for Pointers.
#define UNREACHABLE
This should be used to mark dead code.
const symbol_exprt & to_symbol_expr(const exprt &expr)
Cast an exprt to a symbol_exprt.
const code_typet & to_code_type(const typet &type)
Cast a typet to a code_typet.
bool is_constant(const typet &type)
This method tests, if the given typet is a constant.
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.
exprt get_loop_assigns(const goto_programt::const_targett &loop_end)
Extract loop assigns from annotated loop end.
exprt get_loop_invariants(const goto_programt::const_targett &loop_end, const bool check_side_effect)
Extract loop invariants from annotated loop end.
exprt get_loop_decreases(const goto_programt::const_targett &loop_end, const bool check_side_effect)
Extract loop decreases from annotated loop end.