47 identifier==
"stdin" ||
48 identifier==
"stdout" ||
49 identifier==
"stderr" ||
50 identifier==
"sys_nerr" ||
54 const size_t pos=identifier.find(
"[]");
56 if(
pos!=std::string::npos)
59 identifier.erase(
pos);
74 catch(
const std::string &exception)
106 for(std::map<event_idt, event_idt>::const_iterator
137 for(goto_functionst::function_mapt::const_iterator
158 instrumenter.message.debug()
168 instrumenter.goto_functions.function_map[function_id]);
173 instrumenter.goto_functions.function_map[function_id].body;
181 max_thread=max_thread+1;
182 coming_from=current_thread;
183 current_thread=max_thread;
186 current_thread=coming_from;
187 thread=current_thread;
189 instrumenter.message.debug()
202 #elif defined ATOMIC_FENCE
203 visit_cfg_fence(
i_it, function_id);
206 visit_cfg_propagate(
i_it);
223 else if(
is_fence(instruction, instrumenter.ns))
225 instrumenter.message.debug() <<
"Constructing a fence" <<
messaget::eom;
226 visit_cfg_fence(
i_it, function_id);
228 else if(model!=
TSO &&
is_lwfence(instruction, instrumenter.ns))
230 visit_cfg_lwfence(
i_it, function_id);
232 else if(model==
TSO &&
is_lwfence(instruction, instrumenter.ns))
235 visit_cfg_skip(
i_it);
240 visit_cfg_asm_fence(
i_it, function_id);
244 visit_cfg_function_call(value_sets,
i_it, model,
261#ifdef CONTEXT_INSENSITIVE
264 visit_cfg_propagate(
i_it);
271 visit_cfg_propagate(
i_it);
275 std::pair<unsigned, data_dpt>
new_dp(thread, data_dp);
277 data_dp.print(instrumenter.message);
279 if(instrumenter.goto_functions.function_map[function_id]
280 .body.instructions.empty())
286 goto_programt::instructionst::iterator it =
287 instrumenter.goto_functions.function_map[function_id]
288 .body.instructions.end();
295 goto_programt::instructionst::iterator
i_it)
301 if(in_pos.find(in)!=in_pos.end())
302 for(
const auto &node : in_pos[in])
303 in_pos[
i_it].insert(node);
319 if(instrumenter.map_function_graph.find(
id_function)!=
320 instrumenter.map_function_graph.end())
334 goto_programt::instructionst::iterator
i_it=body.end();
338 goto_programt::instructionst::iterator
targ=body.begin();
344 if(in_pos.find(
targ)!=in_pos.end())
347 if(updated.find(
targ)!=updated.end())
350 for(std::set<nodet>::const_iterator
to=in_pos[
targ].begin();
353 for(std::set<nodet>::const_iterator
from=in_pos[
i_it].begin();
359 instrumenter.message.debug() <<
"else case" <<
messaget::eom;
361 for(goto_programt::instructionst::iterator cur=
i_it;
365 for(
const auto &in : cur->incoming_edges)
368 if(in_pos.find(in)!=in_pos.end() &&
369 updated.find(in)!=updated.end())
374 else if(in_pos.find(in)!=in_pos.end())
383 if(out_pos.find(
targ)!=out_pos.end())
385 for(std::set<nodet>::const_iterator
to=out_pos[
targ].begin();
388 for(std::set<nodet>::const_iterator
from=in_pos[
i_it].begin();
419 instrumenter.message.debug()
420 <<
"contains_shared_array called for " <<
targ->source_location().get_line()
424 instrumenter.message.debug()
425 <<
"Do we have an array at line " << cur->source_location().get_line()
435 instrumenter.message.get_message_handler());
436 instrumenter.message.debug() <<
"Writes: "<<
rw_set.w_entries.size()
442 instrumenter.message.debug() <<
"Is "<<var<<
" an array?"
444 if(
id2string(var).find(
"[]")!=std::string::npos
445 && !instrumenter.local(var))
452 instrumenter.message.debug()<<
"Is "<<var<<
" an array?"<<
messaget::eom;
453 if(
id2string(var).find(
"[]")!=std::string::npos
454 && !instrumenter.local(var))
477 for(
const auto &target :
i_it->targets)
480 if(in_pos.find(target)!=in_pos.end())
482 if(in_pos[
i_it].empty())
510 visit_cfg_duplicate(goto_program, target,
i_it);
512 visit_cfg_backedge(target,
i_it);
522 instrumenter.message.status() <<
"Duplication..." <<
messaget::eom;
527 if(in_pos[
targ].empty())
544 new_targ->source_location().get_function() !=
545 targ->source_location().get_function() ||
546 new_targ->source_location().get_file() !=
547 targ->source_location().get_file())
588 if(updated.find(
targ)!=updated.end())
591 for(std::set<nodet>::const_iterator
to=in_pos[
targ].begin();
593 for(std::set<nodet>::const_iterator
from=in_pos[
i_it].begin();
595 if(
from->first!=
to->first)
599 instrumenter.message.debug() <<
from->first <<
"-po->"
607 instrumenter.message.debug() <<
"else case" <<
messaget::eom;
613 for(
const auto &in : cur->incoming_edges)
615 if(in_pos.find(in)!=in_pos.end()
616 && updated.find(in)!=updated.end())
621 else if(in_pos.find(in)!=in_pos.end())
630 if(out_pos.find(
targ)!=out_pos.end())
632 for(std::set<nodet>::const_iterator
to=out_pos[
targ].begin();
634 for(std::set<nodet>::const_iterator
from=in_pos[
i_it].begin();
636 if(
from->first!=
to->first)
640 instrumenter.message.debug() <<
from->first<<
"-po->"
652 goto_programt::instructionst::iterator
i_it,
664 visit_cfg_propagate(
i_it);
672 instrumenter.message.debug() <<
"backward goto" <<
messaget::eom;
689 goto_programt::instructionst::iterator
i_it,
701 enter_function(fun_id);
702 #ifdef CONTEXT_INSENSITIVE
712 if(instrumenter.map_function_graph.find(fun_id)!=
713 instrumenter.map_function_graph.end())
724 updated.insert(
i_it);
732 fun_id, in_pos[
i_it]);
733 updated.insert(
i_it);
736 leave_function(fun_id);
737 #ifdef CONTEXT_INSENSITIVE
741 catch(
const std::string &s)
743 instrumenter.message.warning() <<
"sorry, doesn't handle recursion "
744 <<
"(function " << fun_id <<
"; .cpp) "
750 goto_programt::instructionst::iterator
i_it,
758 instrumenter.unique_id++,
766 instrumenter.map_vertex_gnode.insert(
770 if(in_pos.find(in)!=in_pos.end())
772 for(
const auto &node : in_pos[in])
774 if(
egraph[node.first].thread!=thread)
776 instrumenter.message.debug() << node.first<<
"-po->"<<
new_fence_node
785 updated.insert(
i_it);
789 goto_programt::instructionst::iterator
i_it,
804 instrumenter.unique_id++,
819 instrumenter.map_vertex_gnode.insert(
823 if(in_pos.find(in)!=in_pos.end())
825 for(
const auto &node : in_pos[in])
827 if(
egraph[node.first].thread!=thread)
829 instrumenter.message.debug() << node.first<<
"-po->"<<
new_fence_node
838 updated.insert(
i_it);
844 goto_programt::instructionst::iterator &
i_it,
863 instrumenter.message.get_message_handler());
865 event_idt previous=std::numeric_limits<event_idt>::max();
873 if(!instruction.
labels.empty() && instruction.
labels.front()==
"ASSERT")
898 instrumenter.unique_id++,
905 instrumenter.message.debug() <<
"new Read" <<
read <<
" @thread" << (thread)
907 << (
local(
read) ?
"local" :
"shared") <<
") #"
915 instrumenter.map_vertex_gnode.insert(
921 if(in_pos.find(in)!=in_pos.end())
923 for(
const auto &node : in_pos[in])
925 if(
egraph[node.first].thread!=thread)
927 instrumenter.message.debug() << node.first<<
"-po->"
940 const std::pair<id2nodet::iterator, id2nodet::iterator>
946 instrumenter.message.debug() <<
id_it->second<<
"<-com->"
948 std::map<event_idt, event_idt>::const_iterator entry=
949 instrumenter.map_vertex_gnode.find(
id_it->second);
950 CHECK_RETURN(entry != instrumenter.map_vertex_gnode.end());
959 for(std::set<event_idt>::const_iterator
id_it=
960 unknown_write_nodes.begin();
961 id_it!=unknown_write_nodes.end();
965 instrumenter.message.debug() << *
id_it<<
"<-com->"
967 std::map<event_idt, event_idt>::const_iterator entry=
968 instrumenter.map_vertex_gnode.find(*
id_it);
969 CHECK_RETURN(entry != instrumenter.map_vertex_gnode.end());
1001 instrumenter.unique_id++,
1009 <<
"new Write " <<
write <<
" @thread" << (thread) <<
"("
1019 instrumenter.map_vertex_gnode.insert(
1023 if(previous!=std::numeric_limits<event_idt>::max())
1025 instrumenter.message.debug() << previous<<
"-po->"<<
new_write_node
1034 if(in_pos.find(in)!=in_pos.end())
1036 for(
const auto &node : in_pos[in])
1038 if(
egraph[node.first].thread!=thread)
1040 instrumenter.message.debug() << node.first<<
"-po->"
1050 const std::pair<id2nodet::iterator, id2nodet::iterator>
1056 instrumenter.message.debug() <<
idr_it->second<<
"<-com->"
1058 std::map<event_idt, event_idt>::const_iterator entry=
1059 instrumenter.map_vertex_gnode.find(
idr_it->second);
1060 CHECK_RETURN(entry != instrumenter.map_vertex_gnode.end());
1069 const std::pair<id2nodet::iterator, id2nodet::iterator>
1075 instrumenter.message.debug() <<
idw_it->second<<
"<-com->"
1077 std::map<event_idt, event_idt>::const_iterator entry=
1078 instrumenter.map_vertex_gnode.find(
idw_it->second);
1079 CHECK_RETURN(entry != instrumenter.map_vertex_gnode.end());
1088 for(std::set<event_idt>::const_iterator
id_it=
1089 unknown_write_nodes.begin();
1090 id_it!=unknown_write_nodes.end();
1094 instrumenter.message.debug() << *
id_it<<
"<-com->"
1096 std::map<event_idt, event_idt>::const_iterator entry=
1097 instrumenter.map_vertex_gnode.find(*
id_it);
1098 CHECK_RETURN(entry != instrumenter.map_vertex_gnode.end());
1107 for(std::set<event_idt>::const_iterator
id_it=
1108 unknown_read_nodes.begin();
1109 id_it!=unknown_read_nodes.end();
1113 instrumenter.message.debug() << *
id_it<<
"<-com->"
1115 std::map<event_idt, event_idt>::const_iterator entry=
1116 instrumenter.map_vertex_gnode.find(*
id_it);
1117 CHECK_RETURN(entry != instrumenter.map_vertex_gnode.end());
1131 if(previous!=std::numeric_limits<event_idt>::max())
1135 updated.insert(
i_it);
1140 visit_cfg_skip(
i_it);
1152 instrumenter.message.debug() <<
"dp: Write:"<<
write<<
"; Read:"<<
read
1179 goto_programt::instructionst::iterator
i_it,
1187 instrumenter.unique_id++,
1195 instrumenter.map_vertex_gnode.insert(
1199 if(in_pos.find(in)!=in_pos.end())
1201 for(
const auto &node : in_pos[in])
1203 instrumenter.message.debug() << node.first<<
"-po->"<<
new_fence_node
1213 updated.insert(
i_it);
1217 updated.insert(
i_it);
1221 goto_programt::instructionst::iterator
i_it)
1223 visit_cfg_propagate(
i_it);
1227 goto_programt::instructionst::iterator it,
1231 it->is_set_return_value() || it->is_throw() || it->is_catch() ||
1232 it->is_skip() || it->is_dead() || it->is_start_thread() ||
1233 it->is_end_thread())
1236 if(it->is_atomic_begin() ||
1237 it->is_atomic_end())
1243 if(it->is_function_call())
1272 for(
const auto &instruction :
gf_entry.second.body.instructions)
1274 if(instruction.source_location() == current_location)
1310 if(
i_it->source_location() == current_location)
1313 for(goto_programt::instructionst::iterator
same_loc =
i_it;
1315 same_loc->source_location() ==
i_it->source_location();
1332 if(it->source_location() == current_location)
1350 if(instruction.is_goto())
1352 for(
const auto &t : instruction.targets)
1379 map.insert(std::make_pair(
1404 for(std::set<event_grapht::critical_cyclet>::iterator
1410 std::set<event_grapht::critical_cyclet>::iterator next=it;
1425 for(std::set<event_grapht::critical_cyclet>::iterator it=
1431 std::set<event_grapht::critical_cyclet>::iterator next=it;
1448 const std::set<event_grapht::critical_cyclet> &set,
1451 std::ofstream &output,
1453 std::ofstream &
table,
1455 bool hide_internals)
1458 std::map<unsigned, std::set<event_idt> >
same_po;
1459 unsigned max_thread=0;
1463 std::map<irep_idt, std::set<event_idt> >
same_file;
1466 std::map<std::string, std::string>
map_id2var;
1467 std::map<std::string, std::string>
map_var2id;
1469 for(std::set<event_grapht::critical_cyclet>::const_iterator it =
1470 set.begin(); it!=set.end(); it++)
1476 ref << it->print_name(model, hide_internals) <<
'\n';
1477 output << it->print_output() <<
'\n';
1482 for(std::list<event_idt>::const_iterator
it_e=it->begin();
1493 if(
ev.thread>max_thread)
1494 max_thread=
ev.thread;
1499 dot <<
ev.id <<
"[label=\"\\\\lb {" <<
ev.id <<
"}";
1500 dot <<
ev.get_operation() <<
"{" <<
ev.variable <<
"} {} @thread";
1501 dot <<
ev.thread <<
"\",color=red,shape=box];\n";
1509 for(
unsigned i=0; i<=max_thread; i++)
1512 dot <<
"{rank=same; thread_" << i
1513 <<
"[shape=plaintext, label=\"thread " << i <<
"\"];";
1514 for(std::set<event_idt>::iterator it=
same_po[i].begin();
1524 for(std::map<
irep_idt, std::set<event_idt> >::const_iterator it=
1529 dot <<
" label=\"" << it->first <<
"\";\n";
1530 for(std::set<event_idt>::const_iterator
ev_it=it->second.begin();
1540 table << std::string(80,
'-');
1541 for(std::map<std::string, std::string>::const_iterator
1549 table << std::string(80,
'-');
1557 std::ofstream output;
1559 std::ofstream
table;
1561 dot.open(
"cycles.dot");
1562 ref.open(
"ref.txt");
1563 output.open(
"output.txt");
1564 all.open(
"all.txt");
1565 table.open(
"table.txt");
1567 dot <<
"digraph G {\n";
1568 dot <<
"nodesep=1; ranksep=1;\n";
1573 model, hide_internals);
1579 std::string name=
"scc_" + std::to_string(i) +
".dot";
1585 table, model, hide_internals);
1589 dot << i <<
"[label=\"SCC " << i <<
"\",link=\"" <<
"scc_" << i;
1612 std::set<event_grapht::critical_cyclet>());
1613 for(std::vector<std::set<event_idt> >::const_iterator it=
egraph_SCCs.begin();
1624 const std::set<event_idt> &filter;
1625 std::set<event_grapht::critical_cyclet> &cycles;
1629 const std::set<event_idt> &
_filter,
1630 std::set<event_grapht::critical_cyclet> &
_cycles)
1643 const std::set<event_idt> &filter=
p_arg->filter;
1644 std::set<event_grapht::critical_cyclet> &cycles=
p_arg->cycles;
1660 std::set<event_grapht::critical_cyclet>());
1662 for(std::vector<std::set<unsigned> >::const_iterator it=
egraph_SCCs.begin();
virtual void clear()
Reset the abstract state.
ait supplies three of the four components needed: an abstract interpreter (in this case handling func...
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
data_typet::const_iterator const_iterator
event_idt copy_segment(event_idt begin, event_idt end)
const wmm_grapht::edgest & po_out(event_idt n) const
void collect_cycles(std::set< critical_cyclet > &set_of_cycles, memory_modelt model, const std::set< event_idt > &filter)
std::map< unsigned, data_dpt > map_data_dp
void add_com_edge(event_idt a, event_idt b)
void add_po_edge(event_idt a, event_idt b)
void add_po_back_edge(event_idt a, event_idt b)
Base class for all expressions.
const source_locationt & source_location() const
The Boolean constant false.
A collection of goto functions.
std::map< irep_idt, goto_functiont > function_mapt
function_mapt function_map
static irep_idt entry_point()
Get the identifier of the entry point to a goto model.
A goto function, consisting of function body (see body) and parameter identifiers (see parameter_iden...
This class represents an instruction in the GOTO intermediate representation.
const goto_instruction_codet & code() const
Get the code represented by this instruction.
bool is_set_return_value() const
bool is_end_thread() const
bool is_start_thread() const
bool is_atomic_end() const
bool is_backwards_goto() const
Returns true if the instruction is a backwards branch.
const exprt & call_function() const
Get the function that is called for FUNCTION_CALL.
bool is_atomic_begin() const
std::set< targett, target_less_than > incoming_edges
bool is_function_call() const
const source_locationt & source_location() const
goto_program_instruction_typet type() const
What kind of instruction?
A generic container class for the GOTO intermediate representation of one function.
instructionst instructions
The list of instructions in the goto program.
instructionst::const_iterator const_targett
std::list< instructiont > instructionst
static instructiont make_assertion(const exprt &g, const source_locationt &l=source_locationt::nil())
std::size_t SCCs(std::vector< node_indext > &subgraph_nr) const
Computes strongly-connected components of a graph and yields a vector expressing a mapping from nodes...
node_indext add_node(arguments &&... values)
void add_edge(node_indext a, node_indext b)
void visit_cfg_backedge(goto_programt::const_targett targ, goto_programt::const_targett i_it)
strategy: fwd/bwd alternation
void visit_cfg_reference_function(irep_idt id_function)
references the first and last edges of the function
bool contains_shared_array(const irep_idt &function_id, goto_programt::const_targett targ, goto_programt::const_targett i_it, value_setst &value_sets) const
instrumentert & instrumenter
virtual void visit_cfg_function(value_setst &value_sets, memory_modelt model, bool no_dependencies, loop_strategyt duplicate_body, const irep_idt &function_id, std::set< nodet > &ending_vertex)
TODO: move the visitor outside, and inherit.
std::pair< irep_idt, event_idt > id2node_pairt
bool local(const irep_idt &i)
void visit_cfg_fence(goto_programt::instructionst::iterator i_it, const irep_idt &function_id)
void visit_cfg_goto(const irep_idt &function_id, const goto_programt &goto_program, goto_programt::instructionst::iterator i_it, loop_strategyt replicate_body, value_setst &value_sets)
void visit_cfg_function_call(value_setst &value_sets, goto_programt::instructionst::iterator i_it, memory_modelt model, bool no_dependenciess, loop_strategyt duplicate_body)
void visit_cfg_lwfence(goto_programt::instructionst::iterator i_it, const irep_idt &function_id)
void visit_cfg_propagate(goto_programt::instructionst::iterator i_it)
void visit_cfg_assign(value_setst &value_sets, const irep_idt &function_id, goto_programt::instructionst::iterator &i_it, bool no_dependencies)
void visit_cfg_duplicate(const goto_programt &goto_program, goto_programt::const_targett targ, goto_programt::const_targett i_it)
void visit_cfg_body(const irep_idt &function_id, const goto_programt &goto_program, goto_programt::const_targett i_it, loop_strategyt replicate_body, value_setst &value_sets)
strategy: fwd/bwd alternation
std::pair< event_idt, event_idt > nodet
void visit_cfg_thread() const
void visit_cfg_skip(goto_programt::instructionst::iterator i_it)
void visit_cfg_asm_fence(goto_programt::instructionst::iterator i_it, const irep_idt &function_id)
void print_outputs(memory_modelt model, bool hide_internals)
void collect_cycles_by_SCCs(memory_modelt model)
Note: can be distributed (#define DISTRIBUTED)
std::set< event_grapht::critical_cyclet > set_of_cycles
std::set< irep_idt > var_to_instr
std::vector< std::set< event_idt > > egraph_SCCs
std::multimap< irep_idt, source_locationt > id2loc
bool is_cfg_spurious(const event_grapht::critical_cyclet &cyc)
goto_functionst & goto_functions
std::map< event_idt, event_idt > map_vertex_gnode
std::vector< std::set< event_grapht::critical_cyclet > > set_of_cycles_per_SCC
void add_instr_to_interleaving(goto_programt::instructionst::iterator it, goto_programt &interleaving)
bool local(const irep_idt &id)
is local variable?
unsigned goto2graph_cfg(value_setst &value_sets, memory_modelt model, bool no_dependencies, loop_strategyt duplicate_body)
goes through CFG and build a static abstract event graph overapproximating the read/write relations f...
void print_outputs_local(const std::set< event_grapht::critical_cyclet > &set, std::ofstream &dot, std::ofstream &ref, std::ofstream &output, std::ofstream &all, std::ofstream &table, memory_modelt model, bool hide_internals)
mstreamt & statistics() const
mstreamt & status() const
bool lookup(const irep_idt &name, const symbolt *&symbol) const override
See documentation for namespace_baset::lookup().
bool has_prefix(const std::string &s, const std::string &prefix)
void dot(const goto_modelt &src, std::ostream &out)
wmm_grapht::node_indext event_idt
bool is_fence(const goto_programt::instructiont &instruction, const namespacet &ns)
bool is_lwfence(const goto_programt::instructiont &instruction, const namespacet &ns)
Fences for instrumentation.
event_idt alt_copy_segment(wmm_grapht &alt_egraph, event_idt begin, event_idt end)
#define add_all_pos(it, target, source)
#define forall_goto_program_instructions(it, program)
#define Forall_goto_program_instructions(it, program)
dstring_hash irep_id_hash
const std::string & id2string(const irep_idt &d)
int __CPROVER_ID java::java io InputStream read
int pthread_join(pthread_t thread, void **value_ptr)
int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg)
Race Detection for Threaded Goto Programs.
#define CHECK_RETURN(CONDITION)
#define INVARIANT(CONDITION, REASON)
This macro uses the wrapper function 'invariant_violated_string'.
#define INITIALIZE_FUNCTION
const symbol_exprt & to_symbol_expr(const exprt &expr)
Cast an exprt to a symbol_exprt.
ssize_t write(int fildes, const void *buf, size_t nbyte)