CBMC
Loading...
Searching...
No Matches
goto2graph.cpp
Go to the documentation of this file.
1/*******************************************************************\
2
3Module: Turns a goto-program into an abstract event graph
4
5Author: Vincent Nimal
6
7Date: 2012
8
9\*******************************************************************/
10
13
14#include "goto2graph.h"
15
16#include <vector>
17#include <string>
18#include <fstream>
19
20#include <util/options.h>
21#include <util/prefix.h>
22
24
26
27#include "fence.h"
28
29// #define PRINT_UNSAFES
30
31
33bool inline instrumentert::local(const irep_idt &id)
34{
35 std::string identifier=id2string(id);
36
37 if(has_prefix(identifier, "symex_invalid") ||
38 has_prefix(identifier, "symex::invalid"))
39 {
40 /* symex_invalid and symex::invalid_object generated when pointer analysis
41 fails */
42 return true;
43 }
44
45 if(identifier==CPROVER_PREFIX "alloc" ||
46 identifier==CPROVER_PREFIX "alloc_size" ||
47 identifier=="stdin" ||
48 identifier=="stdout" ||
49 identifier=="stderr" ||
50 identifier=="sys_nerr" ||
51 has_prefix(identifier, "__unbuffered_"))
52 return true;
53
54 const size_t pos=identifier.find("[]");
55
56 if(pos!=std::string::npos)
57 {
58 /* we don't distinguish the members of an array for the moment */
59 identifier.erase(pos);
60 }
61
62 try
63 {
64 const symbolt &symbol=ns.lookup(identifier);
65
66 if(!symbol.is_static_lifetime)
67 return true; /* these are local */
68
69 if(symbol.is_thread_local)
70 return true; /* these are local */
71
72 return false;
73 }
74 catch(const std::string &exception)
75 {
76 message.debug()<<"Exception: "<<exception << messaget::eom;
77 return false;
78 }
79}
80
82{
83 return instrumenter.local(i);
84}
85
89 value_setst &value_sets,
90 memory_modelt model,
91 bool no_dependencies,
93{
95 message.status() << "Dependencies analysis enabled" << messaget::eom;
96
97 /* builds the graph following the CFG */
98 cfg_visitort visitor(ns, *this);
99 visitor.visit_cfg(value_sets, model, no_dependencies, duplicate_body,
101
102 std::vector<std::size_t> subgraph_index;
104 CHECK_RETURN(egraph_SCCs.empty());
105 egraph_SCCs.resize(num_sccs, std::set<event_idt>());
106 for(std::map<event_idt, event_idt>::const_iterator
107 it=map_vertex_gnode.begin();
108 it!=map_vertex_gnode.end();
109 it++)
110 {
111 const std::size_t sg=subgraph_index[it->second];
112 egraph_SCCs[sg].insert(it->first);
113 }
114
115 message.status() << "Number of threads detected: "
116 << visitor.max_thread << messaget::eom;
117
118 /* SCCs which could host critical cycles */
119 unsigned interesting_sccs=0;
120 for(unsigned i=0; i<num_sccs; i++)
121 if(egraph_SCCs[i].size()>3)
123
124 message.statistics() << "Graph with " << egraph_alt.size() << " nodes has "
125 << interesting_sccs << " interesting SCCs"
126 << messaget::eom;
127
128 message.statistics() << "Number of reads: " << visitor.read_counter
129 << messaget::eom;
130 message.statistics() << "Number of writes: " << visitor.write_counter
131 << messaget::eom;
132 message.statistics() << "Number of wse: " << visitor.ws_counter
133 << messaget::eom;
134 message.statistics() << "Number of rfe/fre: " << visitor.fr_rf_counter
135 << messaget::eom;
136 std::size_t instr_counter=0;
137 for(goto_functionst::function_mapt::const_iterator
138 it=goto_functions.function_map.begin();
140 ++it)
141 instr_counter+=it->second.body.instructions.size();
142 message.statistics() << "Number of goto-instructions: "
144
145 return visitor.max_thread;
146}
147
149 value_setst &value_sets,
150 memory_modelt model,
151 bool no_dependencies,
153 const irep_idt &function_id,
154 std::set<instrumentert::cfg_visitort::nodet> &ending_vertex)
155{
156 /* flow: egraph */
157
158 instrumenter.message.debug()
159 << "visit function " << function_id << messaget::eom;
160
161 if(function_id == INITIALIZE_FUNCTION)
162 {
163 return;
164 }
165
166#ifdef LOCAL_MAY
168 instrumenter.goto_functions.function_map[function_id]);
169#endif
170
171 /* goes through the function */
172 goto_programt &goto_program =
173 instrumenter.goto_functions.function_map[function_id].body;
175 {
176 goto_programt::instructiont &instruction=*i_it;
177
178 /* thread marking */
179 if(instruction.is_start_thread())
180 {
181 max_thread=max_thread+1;
182 coming_from=current_thread;
183 current_thread=max_thread;
184 }
185 else if(instruction.is_end_thread())
186 current_thread=coming_from;
187 thread=current_thread;
188
189 instrumenter.message.debug()
190 << "visit instruction " << instruction.type() << messaget::eom;
191
192 if(instruction.is_start_thread() || instruction.is_end_thread())
193 {
194 /* break the flow */
195 visit_cfg_thread();
196 }
197 else if(instruction.is_atomic_begin() || instruction.is_atomic_end())
198 {
199 /* break the flow (def 1) or add full barrier (def 2) */
200 #ifdef ATOMIC_BREAK
201 visit_cfg_thread();
202 #elif defined ATOMIC_FENCE
203 visit_cfg_fence(i_it, function_id);
204#else
205 /* propagates */
206 visit_cfg_propagate(i_it);
207#endif
208 }
209 /* a:=b -o-> Rb -po-> Wa */
210 else if(instruction.is_assign())
211 {
212 visit_cfg_assign(
213 value_sets,
214 function_id,
215 i_it,
218 ,
220#endif
221 ); // NOLINT(whitespace/parens)
222 }
223 else if(is_fence(instruction, instrumenter.ns))
224 {
225 instrumenter.message.debug() << "Constructing a fence" << messaget::eom;
226 visit_cfg_fence(i_it, function_id);
227 }
228 else if(model!=TSO && is_lwfence(instruction, instrumenter.ns))
229 {
230 visit_cfg_lwfence(i_it, function_id);
231 }
232 else if(model==TSO && is_lwfence(instruction, instrumenter.ns))
233 {
234 /* propagation */
235 visit_cfg_skip(i_it);
236 }
237 else if(
238 instruction.is_other() && instruction.code().get_statement() == ID_fence)
239 {
240 visit_cfg_asm_fence(i_it, function_id);
241 }
242 else if(instruction.is_function_call())
243 {
244 visit_cfg_function_call(value_sets, i_it, model,
246 }
247 else if(instruction.is_goto())
248 {
249 visit_cfg_goto(
250 function_id,
251 goto_program,
252 i_it,
254 value_sets
256 ,
258#endif
259 ); // NOLINT(whitespace/parens)
260 }
261#ifdef CONTEXT_INSENSITIVE
262 else if(instruction.is_set_return_value())
263 {
264 visit_cfg_propagate(i_it);
265 add_all_pos(it, out_nodes[function_id], in_pos[i_it]);
266 }
267#endif
268 else
269 {
270 /* propagates */
271 visit_cfg_propagate(i_it);
272 }
273 }
274
275 std::pair<unsigned, data_dpt> new_dp(thread, data_dp);
276 egraph.map_data_dp.insert(new_dp);
277 data_dp.print(instrumenter.message);
278
279 if(instrumenter.goto_functions.function_map[function_id]
280 .body.instructions.empty())
281 {
282 /* empty set of ending edges */
283 }
284 else
285 {
286 goto_programt::instructionst::iterator it =
287 instrumenter.goto_functions.function_map[function_id]
288 .body.instructions.end();
289 --it;
290 ending_vertex=in_pos[it];
291 }
292}
293
295 goto_programt::instructionst::iterator i_it)
296{
297 const goto_programt::instructiont &instruction=*i_it;
298 /* propagation */
299 in_pos[i_it].clear();
300 for(const auto &in : instruction.incoming_edges)
301 if(in_pos.find(in)!=in_pos.end())
302 for(const auto &node : in_pos[in])
303 in_pos[i_it].insert(node);
304}
305
309
311/* OBSOLETE */
312/* Note: can be merged with visit_cfg_body */
313/* Warning: we iterate here over the successive instructions of the
314 regardless of the gotos. This function has to be called *AFTER*
315 an exploration of the function constructing the graph. */
318{
319 if(instrumenter.map_function_graph.find(id_function)!=
320 instrumenter.map_function_graph.end())
321 return;
322
323 /* gets the body of the function */
324 goto_programt::instructionst &body=instrumenter.goto_functions
325 .function_map[id_function].body.instructions;
326
327 if(body.empty())
328 return;
329
330 /* end of function */
331 /* TODO: ensure that all the returns point to the last statement if the
332 function, or alternatively make i_it point to each return location in
333 the function */
334 goto_programt::instructionst::iterator i_it=body.end();
335 --i_it;
336
337 /* beginning of the function */
338 goto_programt::instructionst::iterator targ=body.begin();
339
340 std::set<event_idt> in_nodes;
341 std::set<event_idt> out_nodes;
342
343 /* if the target has already been covered by fwd analysis */
344 if(in_pos.find(targ)!=in_pos.end())
345 {
346 /* if in_pos was updated at this program point */
347 if(updated.find(targ)!=updated.end())
348 {
349 /* connects the previous nodes to those ones */
350 for(std::set<nodet>::const_iterator to=in_pos[targ].begin();
351 to!=in_pos[targ].end(); ++to)
352 in_nodes.insert(to->first);
353 for(std::set<nodet>::const_iterator from=in_pos[i_it].begin();
354 from!=in_pos[i_it].end(); ++from)
355 out_nodes.insert(from->first);
356 }
357 else
358 {
359 instrumenter.message.debug() << "else case" << messaget::eom;
360 /* connects NEXT nodes following the targets -- bwd analysis */
361 for(goto_programt::instructionst::iterator cur=i_it;
362 cur!=targ; --cur)
363 {
364 instrumenter.message.debug() << "i" << messaget::eom;
365 for(const auto &in : cur->incoming_edges)
366 {
367 instrumenter.message.debug() << "t" << messaget::eom;
368 if(in_pos.find(in)!=in_pos.end() &&
369 updated.find(in)!=updated.end())
370 {
371 /* out_pos[in].insert(in_pos[in])*/
372 add_all_pos(it1, out_pos[in], in_pos[in]);
373 }
374 else if(in_pos.find(in)!=in_pos.end())
375 {
376 /* out_pos[in].insert(out_pos[cur])*/
377 add_all_pos(it2, out_pos[in], out_pos[cur]);
378 }
379 }
380 }
381
382 /* connects the previous nodes to those ones */
383 if(out_pos.find(targ)!=out_pos.end())
384 {
385 for(std::set<nodet>::const_iterator to=out_pos[targ].begin();
386 to!=out_pos[targ].end(); ++to)
387 in_nodes.insert(to->first);
388 for(std::set<nodet>::const_iterator from=in_pos[i_it].begin();
389 from!=in_pos[i_it].end(); ++from)
390 out_nodes.insert(from->first);
391 }
392 }
393 }
394
395 instrumenter.map_function_graph[id_function]=
396 std::make_pair(in_nodes, out_nodes);
397}
398
400 event_idt begin, event_idt end)
401{
402 /* no need to duplicate the loop nodes for the SCC-detection graph -- a
403 single back-edge will ensure the same connectivity */
404 alt_egraph.add_edge(end, begin);
405 return end;
406}
407
409 const irep_idt &function_id,
412 value_setst &value_sets
414 ,
416#endif
417 ) const // NOLINT(whitespace/parens)
418{
419 instrumenter.message.debug()
420 << "contains_shared_array called for " << targ->source_location().get_line()
421 << " and " << i_it->source_location().get_line() << messaget::eom;
422 for(goto_programt::const_targett cur=targ; cur!=i_it; ++cur)
423 {
424 instrumenter.message.debug()
425 << "Do we have an array at line " << cur->source_location().get_line()
426 << "?" << messaget::eom;
428 ns,
429 value_sets,
430 function_id,
431 cur,
433 local_may,
434#endif
435 instrumenter.message.get_message_handler()); // NOLINT(whitespace/parens)
436 instrumenter.message.debug() << "Writes: "<<rw_set.w_entries.size()
437 <<"; Reads:"<<rw_set.r_entries.size() << messaget::eom;
438
439 for(const auto &r_entry : rw_set.r_entries)
440 {
441 const irep_idt var = r_entry.second.object;
442 instrumenter.message.debug() << "Is "<<var<<" an array?"
443 << messaget::eom;
444 if(id2string(var).find("[]")!=std::string::npos
445 && !instrumenter.local(var))
446 return true;
447 }
448
449 for(const auto &w_entry : rw_set.w_entries)
450 {
451 const irep_idt var = w_entry.second.object;
452 instrumenter.message.debug()<<"Is "<<var<<" an array?"<<messaget::eom;
453 if(id2string(var).find("[]")!=std::string::npos
454 && !instrumenter.local(var))
455 return true;
456 }
457 }
458
459 return false;
460}
461
462
465 const irep_idt &function_id,
466 const goto_programt &goto_program,
469 value_setst &value_sets
471 ,
473#endif
474)
475{
476 /* for each target of the goto */
477 for(const auto &target : i_it->targets)
478 {
479 /* if the target has already been covered by fwd analysis */
480 if(in_pos.find(target)!=in_pos.end())
481 {
482 if(in_pos[i_it].empty())
483 continue;
484
485 bool duplicate_this=false;
486
487 switch(replicate_body)
488 {
489 case arrays_only:
490 duplicate_this = contains_shared_array(
491 function_id,
492 target,
493 i_it,
494 value_sets
496 ,
498#endif
499 ); // NOLINT(whitespace/parens)
500 break;
501 case all_loops:
502 duplicate_this=true;
503 break;
504 case no_loop:
505 duplicate_this=false;
506 break;
507 }
508
510 visit_cfg_duplicate(goto_program, target, i_it);
511 else
512 visit_cfg_backedge(target, i_it);
513 }
514 }
515}
516
518 const goto_programt &goto_program,
521{
522 instrumenter.message.status() << "Duplication..." << messaget::eom;
523
524 bool found_pos=false;
526
527 if(in_pos[targ].empty())
528 {
529 /* tries to find the next node after the back edge */
530 for(; new_targ != goto_program.instructions.end(); ++new_targ)
531 {
532 if(in_pos.find(new_targ)!=in_pos.end() && !in_pos[new_targ].empty())
533 {
534 found_pos=true;
535 break;
536 }
537 }
538
539 // The code below uses heuristics to limit false positives: no cycles across
540 // inlined functions, which we would detect when file names or
541 // (user-provided) function names change _within a single goto_program_.
542 if(
543 !found_pos ||
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())
548 return;
549 }
550
551 /* appends the body once more */
552 const std::set<nodet> &up_set=in_pos[(found_pos ? new_targ : targ)];
553 const std::set<nodet> &down_set=in_pos[i_it];
554
555 for(std::set<nodet>::const_iterator begin_it=up_set.begin();
556 begin_it!=up_set.end(); ++begin_it)
557 instrumenter.message.debug() << "Up " << begin_it->first << messaget::eom;
558
559 for(std::set<nodet>::const_iterator begin_it=down_set.begin();
560 begin_it!=down_set.end(); ++begin_it)
561 instrumenter.message.debug() << "Down " << begin_it->first <<messaget::eom;
562
563 for(std::set<nodet>::const_iterator begin_it=up_set.begin();
564 begin_it!=up_set.end(); ++begin_it)
565 {
566 for(std::set<nodet>::const_iterator end_it=down_set.begin();
567 end_it!=down_set.end(); ++end_it)
568 {
569 egraph.copy_segment(begin_it->first, end_it->first);
570 alt_copy_segment(egraph_alt, begin_it->second, end_it->second);
571#if 0
572 const event_idt end=egraph.copy_segment(begin_it->first, end_it->first);
573 const event_idt alt_end=
574 alt_copy_segment(egraph_alt, begin_it->second, end_it->second);
575 // copied; no need for back-edge!
576 // in_pos[i_it].insert(nodet(end, alt_end));
577#endif
578 }
579 }
580}
581
586{
587 /* if in_pos was updated at this program point */
588 if(updated.find(targ)!=updated.end())
589 {
590 /* connects the previous nodes to those ones */
591 for(std::set<nodet>::const_iterator to=in_pos[targ].begin();
592 to!=in_pos[targ].end(); ++to)
593 for(std::set<nodet>::const_iterator from=in_pos[i_it].begin();
594 from!=in_pos[i_it].end(); ++from)
595 if(from->first!=to->first)
596 {
597 if(egraph[from->first].thread!=egraph[to->first].thread)
598 continue;
599 instrumenter.message.debug() << from->first << "-po->"
600 << to->first << messaget::eom;
601 egraph.add_po_back_edge(from->first, to->first);
602 egraph_alt.add_edge(from->second, to->second);
603 }
604 }
605 else
606 {
607 instrumenter.message.debug() << "else case" << messaget::eom;
608
609 /* connects NEXT nodes following the targets -- bwd analysis */
611 cur!=targ; --cur)
612 {
613 for(const auto &in : cur->incoming_edges)
614 {
615 if(in_pos.find(in)!=in_pos.end()
616 && updated.find(in)!=updated.end())
617 {
618 /* out_pos[in].insert(in_pos[in])*/
619 add_all_pos(it1, out_pos[in], in_pos[in]);
620 }
621 else if(in_pos.find(in)!=in_pos.end())
622 {
623 /* out_pos[in].insert(in_pos[cur])*/
624 add_all_pos(it2, out_pos[in], out_pos[cur]);
625 }
626 }
627 }
628
629 /* connects the previous nodes to those ones */
630 if(out_pos.find(targ)!=out_pos.end())
631 {
632 for(std::set<nodet>::const_iterator to=out_pos[targ].begin();
633 to!=out_pos[targ].end(); ++to)
634 for(std::set<nodet>::const_iterator from=in_pos[i_it].begin();
635 from!=in_pos[i_it].end(); ++from)
636 if(from->first!=to->first)
637 {
638 if(egraph[from->first].thread!=egraph[to->first].thread)
639 continue;
640 instrumenter.message.debug() << from->first<<"-po->"
641 <<to->first << messaget::eom;
642 egraph.add_po_back_edge(from->first, to->first);
643 egraph_alt.add_edge(from->second, to->second);
644 }
645 }
646 }
647}
648
650 const irep_idt &function_id,
651 const goto_programt &goto_program,
652 goto_programt::instructionst::iterator i_it,
654 value_setst &value_sets
656 ,
658#endif
659)
660{
661 const goto_programt::instructiont &instruction=*i_it;
662
663 /* propagates */
664 visit_cfg_propagate(i_it);
665
666 /* if back-edges, constructs them too:
667 if goto to event, connects previously propagated events to it;
668 if not, we need to find which events AFTER the target are to
669 be connected. We do a backward analysis. */
670 if(instruction.is_backwards_goto())
671 {
672 instrumenter.message.debug() << "backward goto" << messaget::eom;
673 visit_cfg_body(
674 function_id,
675 goto_program,
676 i_it,
678 value_sets
680 ,
682#endif
683 ); // NOLINT(whitespace/parens)
684 }
685}
686
688 value_setst &value_sets,
689 goto_programt::instructionst::iterator i_it,
690 memory_modelt model,
691 bool no_dependencies,
693{
694 const goto_programt::instructiont &instruction=*i_it;
695
696 const exprt &fun = instruction.call_function();
697 const irep_idt &fun_id=to_symbol_expr(fun).get_identifier();
698 /* ignore recursive calls -- underapproximation */
699 try
700 {
701 enter_function(fun_id);
702 #ifdef CONTEXT_INSENSITIVE
703 stack_fun.push(cur_fun);
704 cur_fun=fun_id;
705 #endif
706
707 #if 0
708 if(!inline_function_cond(fun_id))
709 {
710 /* do not inline it, connect to an existing subgraph or create a new
711 one */
712 if(instrumenter.map_function_graph.find(fun_id)!=
713 instrumenter.map_function_graph.end())
714 {
715 /* connects to existing */
716 /* TODO */
717 }
718 else
719 {
720 /* just inlines */
721 /* TODO */
722 visit_cfg_function(value_sets, model, no_dependencies, fun_id,
723 in_pos[i_it]);
724 updated.insert(i_it);
725 }
726 }
727 else // NOLINT(readability/braces)
728 #endif
729 {
730 /* normal inlining strategy */
731 visit_cfg_function(value_sets, model, no_dependencies, replicate_body,
732 fun_id, in_pos[i_it]);
733 updated.insert(i_it);
734 }
735
736 leave_function(fun_id);
737 #ifdef CONTEXT_INSENSITIVE
738 cur_fun=stack_fun.pop();
739 #endif
740 }
741 catch(const std::string &s)
742 {
743 instrumenter.message.warning() << "sorry, doesn't handle recursion "
744 << "(function " << fun_id << "; .cpp) "
745 << s << messaget::eom;
746 }
747}
748
750 goto_programt::instructionst::iterator i_it,
751 const irep_idt &function_id)
752{
753 const goto_programt::instructiont &instruction=*i_it;
756 thread,
757 "f",
758 instrumenter.unique_id++,
759 instruction.source_location(),
760 function_id,
761 false);
766 instrumenter.map_vertex_gnode.insert(
767 std::make_pair(new_fence_node, new_fence_gnode));
768
769 for(const auto &in : instruction.incoming_edges)
770 if(in_pos.find(in)!=in_pos.end())
771 {
772 for(const auto &node : in_pos[in])
773 {
774 if(egraph[node.first].thread!=thread)
775 continue;
776 instrumenter.message.debug() << node.first<<"-po->"<<new_fence_node
777 << messaget::eom;
778 egraph.add_po_edge(node.first, new_fence_node);
779 egraph_alt.add_edge(node.second, new_fence_gnode);
780 }
781 }
782
783 in_pos[i_it].clear();
784 in_pos[i_it].insert(nodet(new_fence_node, new_fence_gnode));
785 updated.insert(i_it);
786}
787
789 goto_programt::instructionst::iterator i_it,
790 const irep_idt &function_id)
791{
792 const goto_programt::instructiont &instruction=*i_it;
793 bool WRfence = instruction.code().get_bool(ID_WRfence);
794 bool WWfence = instruction.code().get_bool(ID_WWfence);
795 bool RRfence = instruction.code().get_bool(ID_RRfence);
796 bool RWfence = instruction.code().get_bool(ID_RWfence);
797 bool WWcumul = instruction.code().get_bool(ID_WWcumul);
798 bool RRcumul = instruction.code().get_bool(ID_RRcumul);
799 bool RWcumul = instruction.code().get_bool(ID_RWcumul);
802 thread,
803 "asm",
804 instrumenter.unique_id++,
805 instruction.source_location(),
806 function_id,
807 false,
808 WRfence,
809 WWfence,
810 RRfence,
811 RWfence,
812 WWcumul,
813 RWcumul,
814 RRcumul);
819 instrumenter.map_vertex_gnode.insert(
820 std::make_pair(new_fence_node, new_fence_gnode));
821
822 for(const auto &in : instruction.incoming_edges)
823 if(in_pos.find(in)!=in_pos.end())
824 {
825 for(const auto &node : in_pos[in])
826 {
827 if(egraph[node.first].thread!=thread)
828 continue;
829 instrumenter.message.debug() << node.first<<"-po->"<<new_fence_node
830 << messaget::eom;
831 egraph.add_po_edge(node.first, new_fence_node);
832 egraph_alt.add_edge(node.second, new_fence_gnode);
833 }
834 }
835
836 in_pos[i_it].clear();
837 in_pos[i_it].insert(nodet(new_fence_node, new_fence_gnode));
838 updated.insert(i_it);
839}
840
842 value_setst &value_sets,
843 const irep_idt &function_id,
844 goto_programt::instructionst::iterator &i_it,
845 bool no_dependencies
847 ,
849#endif
850)
851{
852 goto_programt::instructiont &instruction=*i_it;
853
854 /* Read (Rb) */
856 ns,
857 value_sets,
858 function_id,
859 i_it,
861 local_may,
862#endif
863 instrumenter.message.get_message_handler()); // NOLINT(whitespace/parens)
864
865 event_idt previous=std::numeric_limits<event_idt>::max();
866 event_idt previous_gnode=std::numeric_limits<event_idt>::max();
867
868#if 0
869 /* for the moment, use labels ASSERT in front of the assertions
870 to prevent them from being instrumented */
871 if(instruction.is_assert())
872 continue; // return;
873 if(!instruction.labels.empty() && instruction.labels.front()=="ASSERT")
874 continue; // return;
875#endif
876
877 for(const auto &r_entry : rw_set.r_entries)
878 {
879 /* creates Read:
880 read is the irep_id of the read in the code;
881 new_read_event is the corresponding abstract event;
882 new_read_node is the node in the graph */
883 const irep_idt &read = r_entry.second.object;
884
885 /* skip local variables */
886 if(local(read))
887 continue;
888
889 read_counter++;
890#if 0
892#endif
893
896 thread,
898 instrumenter.unique_id++,
899 instruction.source_location(),
900 function_id,
901 local(read));
902
905 instrumenter.message.debug() << "new Read" << read << " @thread" << (thread)
906 << "(" << instruction.source_location() << ","
907 << (local(read) ? "local" : "shared") << ") #"
909
910 if(read==ID_unknown)
911 unknown_read_nodes.insert(new_read_node);
912
915 instrumenter.map_vertex_gnode.insert(
916 std::make_pair(new_read_node, new_read_gnode));
917
918 /* creates ... -po-> Read */
919 for(const auto &in : instruction.incoming_edges)
920 {
921 if(in_pos.find(in)!=in_pos.end())
922 {
923 for(const auto &node : in_pos[in])
924 {
925 if(egraph[node.first].thread!=thread)
926 continue;
927 instrumenter.message.debug() << node.first<<"-po->"
929 egraph.add_po_edge(node.first, new_read_node);
930 egraph_alt.add_edge(node.second, new_read_gnode);
931 }
932 }
933 }
934
935 map_reads.insert(id2node_pairt(read, new_read_node));
936 previous=new_read_node;
938
939 /* creates Read <-com-> Write ... */
940 const std::pair<id2nodet::iterator, id2nodet::iterator>
941 with_same_var=map_writes.equal_range(read);
942 for(id2nodet::iterator id_it=with_same_var.first;
943 id_it!=with_same_var.second; id_it++)
944 if(egraph[id_it->second].thread!=new_read_event.thread)
945 {
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());
952 egraph_alt.add_edge(new_read_gnode, entry->second);
954 egraph_alt.add_edge(entry->second, new_read_gnode);
955 ++fr_rf_counter;
956 }
957
958 /* for unknown writes */
959 for(std::set<event_idt>::const_iterator id_it=
960 unknown_write_nodes.begin();
961 id_it!=unknown_write_nodes.end();
962 ++id_it)
963 if(egraph[*id_it].thread!=new_read_event.thread)
964 {
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());
971 egraph_alt.add_edge(new_read_gnode, entry->second);
973 egraph_alt.add_edge(entry->second, new_read_gnode);
974 ++fr_rf_counter;
975 }
976 }
977
978 /* Write (Wa) */
979 for(const auto &w_entry : rw_set.w_entries)
980 {
981 /* creates Write:
982 write is the irep_id in the code;
983 new_write_event is the corresponding abstract event;
984 new_write_node is the node in the graph */
985 const irep_idt &write = w_entry.second.object;
986
987 instrumenter.message.debug() << "WRITE: " << write << messaget::eom;
988
989 /* skip local variables */
990 if(local(write))
991 continue;
992
993 ++write_counter;
994 // assert(write_expr);
995
996 /* creates Write */
999 thread,
1001 instrumenter.unique_id++,
1002 instruction.source_location(),
1003 function_id,
1004 local(write));
1005
1008 instrumenter.message.debug()
1009 << "new Write " << write << " @thread" << (thread) << "("
1010 << instruction.source_location() << ","
1011 << (local(write) ? "local" : "shared") << ") #" << new_write_node
1012 << messaget::eom;
1013
1014 if(write==ID_unknown)
1015 unknown_read_nodes.insert(new_write_node);
1016
1019 instrumenter.map_vertex_gnode.insert(
1020 std::pair<event_idt, event_idt>(new_write_node, new_write_gnode));
1021
1022 /* creates Read -po-> Write */
1023 if(previous!=std::numeric_limits<event_idt>::max())
1024 {
1025 instrumenter.message.debug() << previous<<"-po->"<<new_write_node
1026 << messaget::eom;
1029 }
1030 else
1031 {
1032 for(const auto &in : instruction.incoming_edges)
1033 {
1034 if(in_pos.find(in)!=in_pos.end())
1035 {
1036 for(const auto &node : in_pos[in])
1037 {
1038 if(egraph[node.first].thread!=thread)
1039 continue;
1040 instrumenter.message.debug() << node.first<<"-po->"
1042 egraph.add_po_edge(node.first, new_write_node);
1043 egraph_alt.add_edge(node.second, new_write_gnode);
1044 }
1045 }
1046 }
1047 }
1048
1049 /* creates Write <-com-> Read */
1050 const std::pair<id2nodet::iterator, id2nodet::iterator>
1051 r_with_same_var=map_reads.equal_range(write);
1052 for(id2nodet::iterator idr_it=r_with_same_var.first;
1053 idr_it!=r_with_same_var.second; idr_it++)
1054 if(egraph[idr_it->second].thread!=new_write_event.thread)
1055 {
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());
1062 egraph_alt.add_edge(new_write_gnode, entry->second);
1064 egraph_alt.add_edge(entry->second, new_write_gnode);
1065 ++fr_rf_counter;
1066 }
1067
1068 /* creates Write <-com-> Write */
1069 const std::pair<id2nodet::iterator, id2nodet::iterator>
1070 w_with_same_var=map_writes.equal_range(write);
1071 for(id2nodet::iterator idw_it=w_with_same_var.first;
1072 idw_it!=w_with_same_var.second; idw_it++)
1073 if(egraph[idw_it->second].thread!=new_write_event.thread)
1074 {
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());
1081 egraph_alt.add_edge(new_write_gnode, entry->second);
1083 egraph_alt.add_edge(entry->second, new_write_gnode);
1084 ++ws_counter;
1085 }
1086
1087 /* for unknown writes */
1088 for(std::set<event_idt>::const_iterator id_it=
1089 unknown_write_nodes.begin();
1090 id_it!=unknown_write_nodes.end();
1091 ++id_it)
1092 if(egraph[*id_it].thread!=new_write_event.thread)
1093 {
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());
1100 egraph_alt.add_edge(new_write_gnode, entry->second);
1102 egraph_alt.add_edge(entry->second, new_write_gnode);
1103 ++fr_rf_counter;
1104 }
1105
1106 /* for unknown reads */
1107 for(std::set<event_idt>::const_iterator id_it=
1108 unknown_read_nodes.begin();
1109 id_it!=unknown_read_nodes.end();
1110 ++id_it)
1111 if(egraph[*id_it].thread!=new_write_event.thread)
1112 {
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());
1119 egraph_alt.add_edge(new_write_gnode, entry->second);
1121 egraph_alt.add_edge(entry->second, new_write_gnode);
1122 ++fr_rf_counter;
1123 }
1124
1125
1126 map_writes.insert(id2node_pairt(write, new_write_node));
1127 previous=new_write_node;
1129 }
1130
1131 if(previous!=std::numeric_limits<event_idt>::max())
1132 {
1133 in_pos[i_it].clear();
1134 in_pos[i_it].insert(nodet(previous, previous_gnode));
1135 updated.insert(i_it);
1136 }
1137 else
1138 {
1139 /* propagation */
1140 visit_cfg_skip(i_it);
1141 }
1142
1143 /* data dependency analysis */
1144 if(!no_dependencies)
1145 {
1146 for(const auto &w_entry : rw_set.w_entries)
1147 {
1148 for(const auto &r_entry : rw_set.r_entries)
1149 {
1150 const irep_idt &write = w_entry.second.object;
1151 const irep_idt &read = r_entry.second.object;
1152 instrumenter.message.debug() << "dp: Write:"<<write<<"; Read:"<<read
1153 << messaget::eom;
1154 const datat read_p(read, instruction.source_location());
1155 const datat write_p(write, instruction.source_location());
1156 data_dp.dp_analysis(read_p, local(read), write_p, local(write));
1157 }
1158 }
1159 data_dp.dp_merge();
1160
1161 for(const auto &r_entry : rw_set.r_entries)
1162 {
1163 for(const auto &r_entry2 : rw_set.r_entries)
1164 {
1165 const irep_idt &read2 = r_entry2.second.object;
1166 const irep_idt &read = r_entry.second.object;
1167 if(read2==read)
1168 continue;
1169 const datat read_p(read, instruction.source_location());
1170 const datat read2_p(read2, instruction.source_location());
1171 data_dp.dp_analysis(read_p, local(read), read2_p, local(read2));
1172 }
1173 }
1174 data_dp.dp_merge();
1175 }
1176}
1177
1179 goto_programt::instructionst::iterator i_it,
1180 const irep_idt &function_id)
1181{
1182 const goto_programt::instructiont &instruction=*i_it;
1185 thread,
1186 "F",
1187 instrumenter.unique_id++,
1188 instruction.source_location(),
1189 function_id,
1190 false);
1195 instrumenter.map_vertex_gnode.insert(
1196 std::make_pair(new_fence_node, new_fence_gnode));
1197
1198 for(const auto &in : instruction.incoming_edges)
1199 if(in_pos.find(in)!=in_pos.end())
1200 {
1201 for(const auto &node : in_pos[in])
1202 {
1203 instrumenter.message.debug() << node.first<<"-po->"<<new_fence_node
1204 << messaget::eom;
1205 egraph.add_po_edge(node.first, new_fence_node);
1206 egraph_alt.add_edge(node.second, new_fence_gnode);
1207 }
1208 }
1209#if 0
1210 std::set<nodet> s;
1212 in_pos[i_it]=s;
1213 updated.insert(i_it);
1214#endif
1215 in_pos[i_it].clear();
1216 in_pos[i_it].insert(nodet(new_fence_node, new_fence_gnode));
1217 updated.insert(i_it);
1218}
1219
1221 goto_programt::instructionst::iterator i_it)
1222{
1223 visit_cfg_propagate(i_it);
1224}
1225
1227 goto_programt::instructionst::iterator it,
1229{
1230 if(
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())
1234 return;
1235
1236 if(it->is_atomic_begin() ||
1237 it->is_atomic_end())
1238 {
1239 /* atomicity not checked here for the moment */
1240 return;
1241 }
1242
1243 if(it->is_function_call())
1244 {
1245 /* function call not supported for the moment */
1246 return;
1247 }
1248
1249 /* add this instruction to the interleaving */
1251}
1252
1254{
1255 message.debug() << "spurious by CFG? " << messaget::eom;
1257
1259 e_it!=cyc.end() && ++e_it!=cyc.end(); ++e_it)
1260 {
1261 --e_it;
1262
1264 const source_locationt &current_location=current_event.source_location;
1265
1266 /* select relevant thread (po) -- or function contained in this thread */
1267 goto_programt *current_po=nullptr;
1268 bool thread_found=false;
1269
1271 {
1272 for(const auto &instruction : gf_entry.second.body.instructions)
1273 {
1274 if(instruction.source_location() == current_location)
1275 {
1276 current_po = &gf_entry.second.body;
1277 thread_found=true;
1278 break;
1279 }
1280 }
1281
1282 if(thread_found)
1283 break;
1284 }
1285 INVARIANT(current_po, "thread found");
1286
1289 --e_it;
1290
1291 bool exists_n=false;
1292
1293 for(wmm_grapht::edgest::const_iterator edge_it=pos_cur.begin();
1294 edge_it!=pos_cur.end(); edge_it++)
1295 {
1296 if(pos_next.find(edge_it->first)!=pos_next.end())
1297 {
1298 exists_n=true;
1299 break;
1300 }
1301 }
1302
1303 /* !exists n, has_po_edge(*e_it,n) /\ has_po_edge(*(++it--),n) */
1304 if((++e_it)!=cyc.end() || !exists_n)
1305 {
1306 --e_it;
1307
1308 /* add this instruction to the interleaving */
1310 if(i_it->source_location() == current_location)
1311 {
1312 /* add all the instructions of this line */
1313 for(goto_programt::instructionst::iterator same_loc = i_it;
1314 same_loc != current_po->instructions.end() &&
1315 same_loc->source_location() == i_it->source_location();
1316 same_loc++)
1318 break;
1319 }
1320 }
1321 else
1322 {
1323 --e_it;
1324
1325 /* find the portion of the thread to add */
1326 const abstract_eventt &next_event=egraph[*(++e_it--)];
1327 const source_locationt &next_location=next_event.source_location;
1328
1329 bool in_cycle=false;
1331 {
1332 if(it->source_location() == current_location)
1333 in_cycle=true;
1334
1335 /* do not add the last instruction now -- will be done at
1336 the next iteration */
1337 if(it->source_location() == next_location)
1338 break;
1339
1340 if(in_cycle)
1342 }
1343 }
1344 }
1345
1346 /* if a goto points to a label outside from this interleaving, replace it
1347 by an assert 0 */
1348 for(auto &instruction : interleaving.instructions)
1349 {
1350 if(instruction.is_goto())
1351 {
1352 for(const auto &t : instruction.targets)
1353 {
1354 bool target_in_cycle=false;
1355
1357 {
1358 if(targ==t)
1359 {
1360 target_in_cycle=true;
1361 break;
1362 }
1363 }
1364
1365 if(!target_in_cycle)
1366 {
1367 instruction = goto_programt::make_assertion(
1368 false_exprt(), instruction.source_location());
1369 break;
1370 }
1371 }
1372 }
1373 }
1374
1375 /* now test whether this part of the code can exist */
1378 one_interleaving.body.copy_from(interleaving);
1379 map.insert(std::make_pair(
1381 std::move(one_interleaving)));
1382
1384 this_interleaving.function_map=std::move(map);
1386
1387 #if 0
1388 bmct bmc(no_option, symbol_table, no_message);
1389
1391
1392 message.debug() << "CFG:"<<is_spurious << messaget::eom;
1393 return is_spurious;
1394 #else
1395
1396 return false; // conservative for now
1397 #endif
1398}
1399
1401{
1402 if(!set_of_cycles.empty())
1403 {
1404 for(std::set<event_grapht::critical_cyclet>::iterator
1405 it=set_of_cycles.begin();
1406 it!=set_of_cycles.end();
1407 )
1408 {
1409 bool erased=false;
1410 std::set<event_grapht::critical_cyclet>::iterator next=it;
1411 ++next;
1412 if(is_cfg_spurious(*it))
1413 {
1414 erased=true;
1415 set_of_cycles.erase(it);
1416 }
1417 it=next;
1418 if(!erased)
1419 ++it;
1420 }
1421 }
1422 else if(num_sccs > 0)
1423 {
1424 for(unsigned i=0; i<num_sccs; i++)
1425 for(std::set<event_grapht::critical_cyclet>::iterator it=
1426 set_of_cycles_per_SCC[i].begin();
1427 it!=set_of_cycles_per_SCC[i].end();
1428 )
1429 {
1430 bool erased=false;
1431 std::set<event_grapht::critical_cyclet>::iterator next=it;
1432 ++next;
1433 if(is_cfg_spurious(*it))
1434 {
1435 erased=true;
1436 set_of_cycles_per_SCC[i].erase(it);
1437 }
1438 it=next;
1439 if(!erased)
1440 ++it;
1441 }
1442 }
1443 else
1444 message.status() << "No cycle to filter" << messaget::eom;
1445}
1446
1448 const std::set<event_grapht::critical_cyclet> &set,
1449 std::ofstream &dot,
1450 std::ofstream &ref,
1451 std::ofstream &output,
1452 std::ofstream &all,
1453 std::ofstream &table,
1454 memory_modelt model,
1455 bool hide_internals)
1456{
1457 /* to represent the po aligned in the dot */
1458 std::map<unsigned, std::set<event_idt> > same_po;
1459 unsigned max_thread=0;
1460 unsigned colour=0;
1461
1462 /* to represent the files as clusters */
1463 std::map<irep_idt, std::set<event_idt> > same_file;
1464
1465 /* to summarise in a table all the variables */
1466 std::map<std::string, std::string> map_id2var;
1467 std::map<std::string, std::string> map_var2id;
1468
1469 for(std::set<event_grapht::critical_cyclet>::const_iterator it =
1470 set.begin(); it!=set.end(); it++)
1471 {
1472#ifdef PRINT_UNSAFES
1473 message.debug() << it->print_unsafes() << messaget::eom;
1474#endif
1475 it->print_dot(dot, colour++, model);
1476 ref << it->print_name(model, hide_internals) << '\n';
1477 output << it->print_output() << '\n';
1478 all << it->print_all(model, map_id2var, map_var2id, hide_internals)
1479 << '\n';
1480
1481 /* emphasises instrumented events */
1482 for(std::list<event_idt>::const_iterator it_e=it->begin();
1483 it_e!=it->end(); it_e++)
1484 {
1485 const abstract_eventt &ev=egraph[*it_e];
1486
1488 same_po[ev.thread].insert(*it_e);
1490 same_file[ev.function_id].insert(*it_e);
1491 else if(render_by_file)
1492 same_file[ev.source_location.get_file()].insert(*it_e);
1493 if(ev.thread>max_thread)
1494 max_thread=ev.thread;
1495
1496 if(var_to_instr.find(ev.variable)!=var_to_instr.end()
1497 && id2loc.find(ev.variable)!=id2loc.end())
1498 {
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";
1502 }
1503 }
1504 }
1505
1506 /* aligns events by po */
1508 {
1509 for(unsigned i=0; i<=max_thread; i++)
1510 if(!same_po[i].empty())
1511 {
1512 dot << "{rank=same; thread_" << i
1513 << "[shape=plaintext, label=\"thread " << i << "\"];";
1514 for(std::set<event_idt>::iterator it=same_po[i].begin();
1515 it!=same_po[i].end(); it++)
1516 dot << egraph[*it].id << ";";
1517 dot << "};\n";
1518 }
1519 }
1520
1521 /* clusters events by file/function */
1523 {
1524 for(std::map<irep_idt, std::set<event_idt> >::const_iterator it=
1525 same_file.begin();
1526 it!=same_file.end(); it++)
1527 {
1528 dot << "subgraph cluster_" << irep_id_hash()(it->first) << "{\n";
1529 dot << " label=\"" << it->first << "\";\n";
1530 for(std::set<event_idt>::const_iterator ev_it=it->second.begin();
1531 ev_it!=it->second.end(); ev_it++)
1532 {
1533 dot << " " << egraph[*ev_it].id << ";\n";
1534 }
1535 dot << "};\n";
1536 }
1537 }
1538
1539 /* variable table for "all" */
1540 table << std::string(80, '-');
1541 for(std::map<std::string, std::string>::const_iterator
1542 m_it=map_id2var.begin();
1543 m_it!=map_id2var.end();
1544 ++m_it)
1545 {
1546 table << "\n| " << m_it->first << " : " << m_it->second;
1547 }
1548 table << '\n';
1549 table << std::string(80, '-');
1550 table << '\n';
1551}
1552
1553void instrumentert::print_outputs(memory_modelt model, bool hide_internals)
1554{
1555 std::ofstream dot;
1556 std::ofstream ref;
1557 std::ofstream output;
1558 std::ofstream all;
1559 std::ofstream table;
1560
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");
1566
1567 dot << "digraph G {\n";
1568 dot << "nodesep=1; ranksep=1;\n";
1569
1570 /* prints cycles in the different outputs */
1571 if(!set_of_cycles.empty())
1573 model, hide_internals);
1574 else if(num_sccs!=0)
1575 {
1576 for(unsigned i=0; i<num_sccs; i++)
1577 {
1578 std::ofstream local_dot;
1579 std::string name="scc_" + std::to_string(i) + ".dot";
1580 local_dot.open(name.c_str());
1581
1582 local_dot << "digraph G {\n";
1583 local_dot << "nodesep=1; ranksep=1;\n";
1585 table, model, hide_internals);
1586 local_dot << "}\n";
1587 local_dot.close();
1588
1589 dot << i << "[label=\"SCC " << i << "\",link=\"" << "scc_" << i;
1590 dot << ".svg\"]\n";
1591 }
1592 }
1593 else
1594 message.debug() << "no cycles to output" << messaget::eom;
1595
1596 dot << "}\n";
1597
1598 dot.close();
1599 ref.close();
1600 output.close();
1601 all.close();
1602 table.close();
1603}
1604
1606#if 1
1607// #ifdef _WIN32
1609{
1610 unsigned scc=0;
1612 std::set<event_grapht::critical_cyclet>());
1613 for(std::vector<std::set<event_idt> >::const_iterator it=egraph_SCCs.begin();
1614 it!=egraph_SCCs.end(); it++)
1615 if(it->size()>=4)
1617}
1618#else
1620{
1621public:
1624 const std::set<event_idt> &filter;
1625 std::set<event_grapht::critical_cyclet> &cycles;
1626
1629 const std::set<event_idt> &_filter,
1630 std::set<event_grapht::critical_cyclet> &_cycles)
1631 :instr(_instr), mem(_mem), filter(_filter), cycles(_cycles)
1632 {
1633 }
1634};
1635
1636/* wraper */
1637void *collect_cycles_in_thread(void *arg)
1638{
1639 /* arguments */
1640 pthread_argumentt *p_arg=reinterpret_cast<pthread_argumentt*>(arg);
1642 memory_modelt model=p_arg->mem;
1643 const std::set<event_idt> &filter=p_arg->filter;
1644 std::set<event_grapht::critical_cyclet> &cycles=p_arg->cycles;
1645
1646 this_instrumenter.egraph.collect_cycles(cycles, model, filter);
1647
1648 return NULL;
1649}
1650
1652{
1653 const unsigned number_of_sccs=num_sccs;
1654 std::set<unsigned> interesting_SCCs;
1655
1656 unsigned scc=0;
1657 pthread_t *threads=new pthread_t[num_sccs+1];
1658
1660 std::set<event_grapht::critical_cyclet>());
1661
1662 for(std::vector<std::set<unsigned> >::const_iterator it=egraph_SCCs.begin();
1663 it!=egraph_SCCs.end(); it++)
1664 if(it->size()>=4)
1665 {
1666 interesting_SCCs.insert(scc);
1667 pthread_argumentt arg(*this, model, *it, set_of_cycles_per_SCC[scc]);
1668
1669 int rc=pthread_create(&threads[scc++], NULL,
1671
1672 message.status()<<(rc!=0?"Failure ":"Success ")
1673 <<"in creating thread for SCC #"<<scc-1<<messaget::eom;
1674 }
1675
1676 for(unsigned i=0; i<number_of_sccs; i++)
1677 if(interesting_SCCs.find(i)!=interesting_SCCs.end())
1678 {
1679 int rc=pthread_join(threads[i], NULL);
1680 message.status()<<(rc!=0?"Failure ":"Success ")
1681 <<"in joining thread for SCC #"<<i<<messaget::eom;
1682 }
1683
1684 delete[] threads;
1685}
1686#endif
virtual void clear()
Reset the abstract state.
Definition ai.h:265
ait supplies three of the four components needed: an abstract interpreter (in this case handling func...
Definition ai.h:562
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition dstring.h:38
data_typet::const_iterator const_iterator
Definition event_graph.h:70
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)
messaget & message
void add_po_edge(event_idt a, event_idt b)
void add_po_back_edge(event_idt a, event_idt b)
event_idt add_node()
Base class for all expressions.
Definition expr.h:56
const source_locationt & source_location() const
Definition expr.h:231
The Boolean constant false.
Definition std_expr.h:3200
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_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.
std::set< targett, target_less_than > incoming_edges
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...
Definition graph.h:832
nodet::edgest edgest
Definition graph.h:170
node_indext add_node(arguments &&... values)
Definition graph.h:180
void add_edge(node_indext a, node_indext b)
Definition graph.h:232
std::size_t size() const
Definition graph.h:212
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
Definition goto2graph.h:90
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
Definition goto2graph.h:181
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
Definition goto2graph.h:190
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)
unsigned num_sccs
Definition goto2graph.h:319
void collect_cycles_by_SCCs(memory_modelt model)
Note: can be distributed (#define DISTRIBUTED)
event_grapht egraph
Definition goto2graph.h:309
std::set< event_grapht::critical_cyclet > set_of_cycles
Definition goto2graph.h:315
bool render_po_aligned
Definition goto2graph.h:45
std::set< irep_idt > var_to_instr
Definition goto2graph.h:353
std::vector< std::set< event_idt > > egraph_SCCs
Definition goto2graph.h:312
std::multimap< irep_idt, source_locationt > id2loc
Definition goto2graph.h:354
bool is_cfg_spurious(const event_grapht::critical_cyclet &cyc)
bool render_by_function
Definition goto2graph.h:47
goto_functionst & goto_functions
Definition goto2graph.h:36
bool render_by_file
Definition goto2graph.h:46
std::map< event_idt, event_idt > map_vertex_gnode
Definition goto2graph.h:39
namespacet ns
Definition goto2graph.h:33
std::vector< std::set< event_grapht::critical_cyclet > > set_of_cycles_per_SCC
Definition goto2graph.h:318
wmm_grapht egraph_alt
Definition goto2graph.h:40
void add_instr_to_interleaving(goto_programt::instructionst::iterator it, goto_programt &interleaving)
messaget & message
Definition goto2graph.h:306
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 cfg_cycles_filter()
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 & debug() const
Definition message.h:421
mstreamt & statistics() const
Definition message.h:411
static eomt eom
Definition message.h:289
mstreamt & status() const
Definition message.h:406
bool lookup(const irep_idt &name, const symbolt *&symbol) const override
See documentation for namespace_baset::lookup().
Symbol table entry.
Definition symbol.h:28
bool is_static_lifetime
Definition symbol.h:70
bool is_thread_local
Definition symbol.h:71
bool has_prefix(const std::string &s, const std::string &prefix)
Definition converter.cpp:13
#define CPROVER_PREFIX
void dot(const goto_modelt &src, std::ostream &out)
Definition dot.cpp:359
wmm_grapht::node_indext event_idt
Definition event_graph.h:32
bool is_fence(const goto_programt::instructiont &instruction, const namespacet &ns)
Definition fence.cpp:19
bool is_lwfence(const goto_programt::instructiont &instruction, const namespacet &ns)
Definition fence.cpp:35
Fences for instrumentation.
event_idt alt_copy_segment(wmm_grapht &alt_egraph, event_idt begin, event_idt end)
Instrumenter.
#define add_all_pos(it, target, source)
Definition goto2graph.h:204
#define forall_goto_program_instructions(it, program)
#define Forall_goto_program_instructions(it, program)
dstring_hash irep_id_hash
Definition irep.h:38
const std::string & id2string(const irep_idt &d)
Definition irep.h:44
int __CPROVER_ID java::java io InputStream read
Definition java.io.c:5
literalt pos(literalt a)
Definition literal.h:194
Options.
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)
Definition invariant.h:495
#define INVARIANT(CONDITION, REASON)
This macro uses the wrapper function 'invariant_violated_string'.
Definition invariant.h:423
#define INITIALIZE_FUNCTION
const symbol_exprt & to_symbol_expr(const exprt &expr)
Cast an exprt to a symbol_exprt.
Definition std_expr.h:272
ssize_t write(int fildes, const void *buf, size_t nbyte)
Definition unistd.c:195
memory_modelt
Definition wmm.h:18
@ TSO
Definition wmm.h:20
loop_strategyt
Definition wmm.h:37
@ all_loops
Definition wmm.h:39
@ arrays_only
Definition wmm.h:38
@ no_loop
Definition wmm.h:40
@ all
Definition wmm.h:28