cprover
change_impact.cpp
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Data and control-dependencies of syntactic diff
4 
5 Author: Michael Tautschnig
6 
7 Date: April 2016
8 
9 \*******************************************************************/
10 
13 
14 #include "change_impact.h"
15 
16 #include <iostream>
17 
19 
21 
22 #include "unified_diff.h"
23 
24 #if 0
25  struct cfg_nodet
26  {
27  cfg_nodet():node_required(false)
28  {
29  }
30 
31  bool node_required;
32 #ifdef DEBUG_FULL_SLICERT
33  std::set<unsigned> required_by;
34 #endif
35  };
36 
37  typedef cfg_baset<cfg_nodet> cfgt;
38  cfgt cfg;
39 
40  typedef std::vector<cfgt::entryt> dep_node_to_cfgt;
41  typedef std::stack<cfgt::entryt> queuet;
42 
43  inline void add_to_queue(
44  queuet &queue,
45  const cfgt::entryt &entry,
47  {
48 #ifdef DEBUG_FULL_SLICERT
49  cfg[entry].required_by.insert(reason->location_number);
50 #endif
51  queue.push(entry);
52  }
53 
55  goto_functionst &goto_functions,
56  const namespacet &ns,
57  slicing_criteriont &criterion)
58 {
59  // build the CFG data structure
60  cfg(goto_functions);
61 
62  // fill queue with according to slicing criterion
63  queuet queue;
64  // gather all unconditional jumps as they may need to be included
65  jumpst jumps;
66  // declarations or dead instructions may be necessary as well
67  decl_deadt decl_dead;
68 
69  for(const auto &entry : cfg.entries())
70  {
71  const auto &instruction = instruction_and_index.first;
72  const auto instruction_node_index = instruction_and_index.second;
73  if(criterion(instruction))
74  add_to_queue(queue, instruction_node_index, instruction);
75  else if(implicit(instruction))
76  add_to_queue(queue, instruction_node_index, instruction);
77  else if((instruction->is_goto() && instruction->guard.is_true()) ||
78  instruction->is_throw())
79  jumps.push_back(instruction_node_index);
80  else if(instruction->is_decl())
81  {
82  const auto &s=to_code_decl(instruction->code).symbol();
83  decl_dead[s.get_identifier()].push(instruction_node_index);
84  }
85  else if(instruction->is_dead())
86  {
87  const auto &s=to_code_dead(instruction->code).symbol();
88  decl_dead[s.get_identifier()].push(instruction_node_index);
89  }
90  }
91 
92  // compute program dependence graph (and post-dominators)
93  dependence_grapht dep_graph(ns);
94  dep_graph(goto_functions, ns);
95 
96  // compute the fixedpoint
97  fixedpoint(goto_functions, queue, jumps, decl_dead, dep_graph);
98 
99  // now replace those instructions that are not needed
100  // by skips
101 
102  Forall_goto_functions(f_it, goto_functions)
103  if(f_it->second.body_available())
104  {
105  Forall_goto_program_instructions(i_it, f_it->second.body)
106  {
107  const auto &node = cfg.get_node(i_it);
108  if(!i_it->is_end_function() && // always retained
109  !node.node_required)
110  i_it->make_skip();
111 #ifdef DEBUG_FULL_SLICERT
112  else
113  {
114  std::string c="ins:"+std::to_string(i_it->location_number);
115  c+=" req by:";
116  for(std::set<unsigned>::const_iterator
117  req_it=node.required_by.begin();
118  req_it!=node.required_by.end();
119  ++req_it)
120  {
121  if(req_it!=node.required_by.begin())
122  c+=",";
123  c+=std::to_string(*req_it);
124  }
125  i_it->source_location.set_column(c); // for show-goto-functions
126  i_it->source_location.set_comment(c); // for dump-c
127  }
128 #endif
129  }
130  }
131 
132  // remove the skips
133  remove_skip(goto_functions);
134 }
135 
136 
138  goto_functionst &goto_functions,
139  queuet &queue,
140  jumpst &jumps,
141  decl_deadt &decl_dead,
142  const dependence_grapht &dep_graph)
143 {
144  std::vector<cfgt::entryt> dep_node_to_cfg;
145  dep_node_to_cfg.reserve(dep_graph.size());
146 
147  for(unsigned i=0; i<dep_graph.size(); ++i)
148  {
149  dep_node_to_cfg.push_back(cfg.get_node_index(dep_graph[i].PC));
150  }
151 
152  // process queue until empty
153  while(!queue.empty())
154  {
155  while(!queue.empty())
156  {
157  cfgt::entryt e=queue.top();
158  cfgt::nodet &node=cfg[e];
159  queue.pop();
160 
161  // already done by some earlier iteration?
162  if(node.node_required)
163  continue;
164 
165  // node is required
166  node.node_required=true;
167 
168  // add data and control dependencies of node
169  add_dependencies(node, queue, dep_graph, dep_node_to_cfg);
170 
171  // retain all calls of the containing function
172  add_function_calls(node, queue, goto_functions);
173 
174  // find all the symbols it uses to add declarations
175  add_decl_dead(node, queue, decl_dead);
176  }
177 
178  // add any required jumps
179  add_jumps(queue, jumps, dep_graph.cfg_post_dominators());
180  }
181 }
182 
183 
185  const cfgt::nodet &node,
186  queuet &queue,
187  const dependence_grapht &dep_graph,
188  const dep_node_to_cfgt &dep_node_to_cfg)
189 {
190  const dependence_grapht::nodet &d_node=
191  dep_graph[dep_graph[node.PC].get_node_id()];
192 
193  for(dependence_grapht::edgest::const_iterator
194  it=d_node.in.begin();
195  it!=d_node.in.end();
196  ++it)
197  add_to_queue(queue, dep_node_to_cfg[it->first], node.PC);
198 }
199 #endif
200 
202 {
203 public:
205  const goto_modelt &model_old,
206  const goto_modelt &model_new,
208  bool compact_output);
209 
210  void operator()();
211 
212 protected:
215 
220 
222 
225 
227  {
228  SAME=0,
229  NEW=1<<0,
230  DELETED=1<<1,
234  DEL_CTRL_DEP=1<<5
235  };
236 
237  typedef std::map<goto_programt::const_targett, unsigned>
239  typedef std::map<irep_idt, goto_program_change_impactt>
241 
243 
244  void change_impact(const irep_idt &function_id);
245 
246  void change_impact(
247  const irep_idt &function_id,
248  const goto_programt &old_goto_program,
249  const goto_programt &new_goto_program,
251  goto_program_change_impactt &old_impact,
252  goto_program_change_impactt &new_impact);
253 
254  void propogate_dep_back(
255  const irep_idt &function_id,
256  const dependence_grapht::nodet &d_node,
257  const dependence_grapht &dep_graph,
259  bool del);
261  const irep_idt &function_id,
262  const dependence_grapht::nodet &d_node,
263  const dependence_grapht &dep_graph,
265  bool del);
266 
268  const irep_idt &function_id,
269  const goto_program_change_impactt &c_i,
270  const goto_functionst &goto_functions,
271  const namespacet &ns) const;
273  const irep_idt &function_id,
274  const goto_program_change_impactt &o_c_i,
275  const goto_functionst &o_goto_functions,
276  const namespacet &o_ns,
277  const goto_program_change_impactt &n_c_i,
278  const goto_functionst &n_goto_functions,
279  const namespacet &n_ns) const;
280 
281  void output_instruction(
282  char prefix,
283  const goto_programt &goto_program,
284  const namespacet &ns,
285  const irep_idt &function_id,
286  goto_programt::const_targett &target) const;
287 };
288 
290  const goto_modelt &model_old,
291  const goto_modelt &model_new,
292  impact_modet _impact_mode,
293  bool _compact_output):
294  impact_mode(_impact_mode),
295  compact_output(_compact_output),
296  old_goto_functions(model_old.goto_functions),
297  ns_old(model_old.symbol_table),
298  new_goto_functions(model_new.goto_functions),
299  ns_new(model_new.symbol_table),
300  unified_diff(model_old, model_new),
301  old_dep_graph(ns_old),
302  new_dep_graph(ns_new)
303 {
304  // syntactic difference?
305  if(!unified_diff())
306  return;
307 
308  // compute program dependence graph of old code
310 
311  // compute program dependence graph of new code
313 }
314 
315 void change_impactt::change_impact(const irep_idt &function_id)
316 {
318 
319  if(diff.empty())
320  return;
321 
322  goto_functionst::function_mapt::const_iterator old_fit =
323  old_goto_functions.function_map.find(function_id);
324  goto_functionst::function_mapt::const_iterator new_fit =
325  new_goto_functions.function_map.find(function_id);
326 
327  goto_programt empty;
328 
329  const goto_programt &old_goto_program=
330  old_fit==old_goto_functions.function_map.end() ?
331  empty :
332  old_fit->second.body;
333  const goto_programt &new_goto_program=
334  new_fit==new_goto_functions.function_map.end() ?
335  empty :
336  new_fit->second.body;
337 
339  function_id,
340  old_goto_program,
341  new_goto_program,
342  diff,
343  old_change_impact[function_id],
344  new_change_impact[function_id]);
345 }
346 
348  const irep_idt &function_id,
349  const goto_programt &old_goto_program,
350  const goto_programt &new_goto_program,
352  goto_program_change_impactt &old_impact,
353  goto_program_change_impactt &new_impact)
354 {
356  old_goto_program.instructions.begin();
358  new_goto_program.instructions.begin();
359 
360  for(const auto &d : diff)
361  {
362  switch(d.second)
363  {
365  assert(o_it!=old_goto_program.instructions.end());
366  assert(n_it!=new_goto_program.instructions.end());
367  old_impact[o_it]|=SAME;
368  ++o_it;
369  assert(n_it==d.first);
370  new_impact[n_it]|=SAME;
371  ++n_it;
372  break;
374  assert(o_it!=old_goto_program.instructions.end());
375  assert(o_it==d.first);
376  {
377  const dependence_grapht::nodet &d_node=
378  old_dep_graph[old_dep_graph[o_it].get_node_id()];
379 
383  function_id, d_node, old_dep_graph, old_change_impact, true);
387  function_id, d_node, old_dep_graph, old_change_impact, true);
388  }
389  old_impact[o_it]|=DELETED;
390  ++o_it;
391  break;
393  assert(n_it!=new_goto_program.instructions.end());
394  assert(n_it==d.first);
395  {
396  const dependence_grapht::nodet &d_node=
397  new_dep_graph[new_dep_graph[n_it].get_node_id()];
398 
401  {
403  function_id, d_node, new_dep_graph, new_change_impact, false);
404  }
407  {
409  function_id, d_node, new_dep_graph, new_change_impact, false);
410  }
411  }
412  new_impact[n_it]|=NEW;
413  ++n_it;
414  break;
415  }
416  }
417 }
418 
420  const irep_idt &function_id,
421  const dependence_grapht::nodet &d_node,
422  const dependence_grapht &dep_graph,
424  bool del)
425 {
426  for(dependence_grapht::edgest::const_iterator it = d_node.out.begin();
427  it != d_node.out.end(); ++it)
428  {
429  goto_programt::const_targett src = dep_graph[it->first].PC;
430 
431  mod_flagt data_flag = del ? DEL_DATA_DEP : NEW_DATA_DEP;
432  mod_flagt ctrl_flag = del ? DEL_CTRL_DEP : NEW_CTRL_DEP;
433 
434  if(
435  (change_impact[function_id][src] & data_flag) ||
436  (change_impact[function_id][src] & ctrl_flag))
437  continue;
438  if(it->second.get() == dep_edget::kindt::DATA
439  || it->second.get() == dep_edget::kindt::BOTH)
440  change_impact[function_id][src] |= data_flag;
441  else
442  change_impact[function_id][src] |= ctrl_flag;
444  function_id,
445  dep_graph[dep_graph[src].get_node_id()],
446  dep_graph,
448  del);
449  }
450 }
451 
453  const irep_idt &function_id,
454  const dependence_grapht::nodet &d_node,
455  const dependence_grapht &dep_graph,
457  bool del)
458 {
459  for(dependence_grapht::edgest::const_iterator it = d_node.in.begin();
460  it != d_node.in.end(); ++it)
461  {
462  goto_programt::const_targett src = dep_graph[it->first].PC;
463 
464  mod_flagt data_flag = del ? DEL_DATA_DEP : NEW_DATA_DEP;
465  mod_flagt ctrl_flag = del ? DEL_CTRL_DEP : NEW_CTRL_DEP;
466 
467  if(
468  (change_impact[function_id][src] & data_flag) ||
469  (change_impact[function_id][src] & ctrl_flag))
470  {
471  continue;
472  }
473  if(it->second.get() == dep_edget::kindt::DATA
474  || it->second.get() == dep_edget::kindt::BOTH)
475  change_impact[function_id][src] |= data_flag;
476  else
477  change_impact[function_id][src] |= ctrl_flag;
478 
480  function_id,
481  dep_graph[dep_graph[src].get_node_id()],
482  dep_graph,
484  del);
485  }
486 }
487 
489 {
490  // sorted iteration over intersection(old functions, new functions)
491  typedef std::map<irep_idt,
492  goto_functionst::function_mapt::const_iterator>
493  function_mapt;
494 
495  function_mapt old_funcs, new_funcs;
496 
498  old_funcs.insert(std::make_pair(it->first, it));
500  new_funcs.insert(std::make_pair(it->first, it));
501 
502  function_mapt::const_iterator ito=old_funcs.begin();
503  for(function_mapt::const_iterator itn=new_funcs.begin();
504  itn!=new_funcs.end();
505  ++itn)
506  {
507  while(ito!=old_funcs.end() && ito->first<itn->first)
508  ++ito;
509 
510  if(ito!=old_funcs.end() && itn->first==ito->first)
511  {
512  change_impact(itn->first);
513 
514  ++ito;
515  }
516  }
517 
518  goto_functions_change_impactt::const_iterator oc_it=
519  old_change_impact.begin();
520  for(goto_functions_change_impactt::const_iterator
521  nc_it=new_change_impact.begin();
522  nc_it!=new_change_impact.end();
523  ++nc_it)
524  {
525  for( ;
526  oc_it!=old_change_impact.end() && oc_it->first<nc_it->first;
527  ++oc_it)
529  oc_it->first,
530  oc_it->second,
532  ns_old);
533 
534  if(oc_it==old_change_impact.end() || nc_it->first<oc_it->first)
536  nc_it->first,
537  nc_it->second,
539  ns_new);
540  else
541  {
542  assert(oc_it->first==nc_it->first);
543 
545  nc_it->first,
546  oc_it->second,
548  ns_old,
549  nc_it->second,
551  ns_new);
552 
553  ++oc_it;
554  }
555  }
556 }
557 
559  const irep_idt &function_id,
560  const goto_program_change_impactt &c_i,
561  const goto_functionst &goto_functions,
562  const namespacet &ns) const
563 {
564  goto_functionst::function_mapt::const_iterator f_it =
565  goto_functions.function_map.find(function_id);
566  assert(f_it!=goto_functions.function_map.end());
567  const goto_programt &goto_program=f_it->second.body;
568 
569  if(!compact_output)
570  std::cout << "/** " << function_id << " **/\n";
571 
572  forall_goto_program_instructions(target, goto_program)
573  {
574  goto_program_change_impactt::const_iterator c_entry=
575  c_i.find(target);
576  const unsigned mod_flags =
577  c_entry == c_i.end() ? static_cast<unsigned>(SAME) : c_entry->second;
578 
579  char prefix = ' ';
580  // syntactic changes are preferred over data/control-dependence
581  // modifications
582  if(mod_flags==SAME)
583  prefix=' ';
584  else if(mod_flags&DELETED)
585  prefix='-';
586  else if(mod_flags&NEW)
587  prefix='+';
588  else if(mod_flags&NEW_DATA_DEP)
589  prefix='D';
590  else if(mod_flags&NEW_CTRL_DEP)
591  prefix='C';
592  else if(mod_flags&DEL_DATA_DEP)
593  prefix='d';
594  else if(mod_flags&DEL_CTRL_DEP)
595  prefix='c';
596  else
597  UNREACHABLE;
598 
599  output_instruction(prefix, goto_program, ns, function_id, target);
600  }
601 }
602 
604  const irep_idt &function_id,
605  const goto_program_change_impactt &o_c_i,
606  const goto_functionst &o_goto_functions,
607  const namespacet &o_ns,
608  const goto_program_change_impactt &n_c_i,
609  const goto_functionst &n_goto_functions,
610  const namespacet &n_ns) const
611 {
612  goto_functionst::function_mapt::const_iterator o_f_it =
613  o_goto_functions.function_map.find(function_id);
614  assert(o_f_it!=o_goto_functions.function_map.end());
615  const goto_programt &old_goto_program=o_f_it->second.body;
616 
617  goto_functionst::function_mapt::const_iterator f_it =
618  n_goto_functions.function_map.find(function_id);
619  assert(f_it!=n_goto_functions.function_map.end());
620  const goto_programt &goto_program=f_it->second.body;
621 
622  if(!compact_output)
623  std::cout << "/** " << function_id << " **/\n";
624 
626  old_goto_program.instructions.begin();
627  forall_goto_program_instructions(target, goto_program)
628  {
629  goto_program_change_impactt::const_iterator o_c_entry=
630  o_c_i.find(o_target);
631  const unsigned old_mod_flags = o_c_entry == o_c_i.end()
632  ? static_cast<unsigned>(SAME)
633  : o_c_entry->second;
634 
635  if(old_mod_flags&DELETED)
636  {
637  output_instruction('-', goto_program, o_ns, function_id, o_target);
638  ++o_target;
639  --target;
640  continue;
641  }
642 
643  goto_program_change_impactt::const_iterator c_entry=
644  n_c_i.find(target);
645  const unsigned mod_flags =
646  c_entry == n_c_i.end() ? static_cast<unsigned>(SAME) : c_entry->second;
647 
648  char prefix = ' ';
649  // syntactic changes are preferred over data/control-dependence
650  // modifications
651  if(mod_flags==SAME)
652  {
653  if(old_mod_flags==SAME)
654  prefix=' ';
655  else if(old_mod_flags&DEL_DATA_DEP)
656  prefix='d';
657  else if(old_mod_flags&DEL_CTRL_DEP)
658  prefix='c';
659  else
660  UNREACHABLE;
661 
662  ++o_target;
663  }
664  else if(mod_flags&DELETED)
665  UNREACHABLE;
666  else if(mod_flags&NEW)
667  prefix='+';
668  else if(mod_flags&NEW_DATA_DEP)
669  {
670  prefix='D';
671 
672  assert(old_mod_flags==SAME ||
673  old_mod_flags&DEL_DATA_DEP ||
674  old_mod_flags&DEL_CTRL_DEP);
675  ++o_target;
676  }
677  else if(mod_flags&NEW_CTRL_DEP)
678  {
679  prefix='C';
680 
681  assert(old_mod_flags==SAME ||
682  old_mod_flags&DEL_DATA_DEP ||
683  old_mod_flags&DEL_CTRL_DEP);
684  ++o_target;
685  }
686  else
687  UNREACHABLE;
688 
689  output_instruction(prefix, goto_program, n_ns, function_id, target);
690  }
691  for( ;
692  o_target!=old_goto_program.instructions.end();
693  ++o_target)
694  {
695  goto_program_change_impactt::const_iterator o_c_entry=
696  o_c_i.find(o_target);
697  const unsigned old_mod_flags = o_c_entry == o_c_i.end()
698  ? static_cast<unsigned>(SAME)
699  : o_c_entry->second;
700 
701  char prefix = ' ';
702  // syntactic changes are preferred over data/control-dependence
703  // modifications
704  if(old_mod_flags==SAME)
705  UNREACHABLE;
706  else if(old_mod_flags&DELETED)
707  prefix='-';
708  else if(old_mod_flags&NEW)
709  UNREACHABLE;
710  else if(old_mod_flags&DEL_DATA_DEP)
711  prefix='d';
712  else if(old_mod_flags&DEL_CTRL_DEP)
713  prefix='c';
714  else
715  UNREACHABLE;
716 
717  output_instruction(prefix, goto_program, o_ns, function_id, o_target);
718  }
719 }
720 
722  char prefix,
723  const goto_programt &goto_program,
724  const namespacet &ns,
725  const irep_idt &function_id,
726  goto_programt::const_targett &target) const
727 {
728  if(compact_output)
729  {
730  if(prefix == ' ')
731  return;
732  const irep_idt &file=target->source_location.get_file();
733  const irep_idt &line=target->source_location.get_line();
734  if(!file.empty() && !line.empty())
735  std::cout << prefix << " " << id2string(file)
736  << " " << id2string(line) << '\n';
737  }
738  else
739  {
740  std::cout << prefix;
741  goto_program.output_instruction(ns, function_id, std::cout, *target);
742  }
743 }
744 
746  const goto_modelt &model_old,
747  const goto_modelt &model_new,
748  impact_modet impact_mode,
749  bool compact_output)
750 {
751  change_impactt c(model_old, model_new, impact_mode, compact_output);
752  c();
753 }
Forall_goto_program_instructions
#define Forall_goto_program_instructions(it, program)
Definition: goto_program.h:1201
UNREACHABLE
#define UNREACHABLE
This should be used to mark dead code.
Definition: invariant.h:504
dstringt
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:37
impact_modet
impact_modet
Definition: change_impact.h:18
change_impactt::output_instruction
void output_instruction(char prefix, const goto_programt &goto_program, const namespacet &ns, const irep_idt &function_id, goto_programt::const_targett &target) const
Definition: change_impact.cpp:721
grapht::size
std::size_t size() const
Definition: graph.h:213
change_impactt::operator()
void operator()()
Definition: change_impact.cpp:488
change_impactt::goto_program_change_impactt
std::map< goto_programt::const_targett, unsigned > goto_program_change_impactt
Definition: change_impact.cpp:238
dependence_grapht
Definition: dependence_graph.h:217
to_code_decl
const code_declt & to_code_decl(const codet &code)
Definition: std_code.h:450
impact_modet::BACKWARD
@ BACKWARD
change_impactt::old_change_impact
goto_functions_change_impactt old_change_impact
Definition: change_impact.cpp:242
slicing_criteriont
Definition: full_slicer.h:33
cfg_baset< cfg_nodet >::entryt
base_grapht::node_indext entryt
Definition: cfg.h:91
remove_skip
void remove_skip(goto_programt &goto_program, goto_programt::targett begin, goto_programt::targett end)
remove unnecessary skip statements
Definition: remove_skip.cpp:85
change_impactt::new_goto_functions
const goto_functionst & new_goto_functions
Definition: change_impact.cpp:218
change_impactt::propogate_dep_forward
void propogate_dep_forward(const irep_idt &function_id, const dependence_grapht::nodet &d_node, const dependence_grapht &dep_graph, goto_functions_change_impactt &change_impact, bool del)
Definition: change_impact.cpp:419
dependence_grapht::cfg_post_dominators
const post_dominators_mapt & cfg_post_dominators() const
Definition: dependence_graph.h:262
file
Definition: kdev_t.h:19
goto_model.h
Symbol Table + CFG.
change_impact
void change_impact(const goto_modelt &model_old, const goto_modelt &model_new, impact_modet impact_mode, bool compact_output)
Definition: change_impact.cpp:745
unified_difft::differencet::SAME
@ SAME
goto_modelt
Definition: goto_model.h:26
change_impactt::ns_old
const namespacet ns_old
Definition: change_impact.cpp:217
change_impactt::NEW_DATA_DEP
@ NEW_DATA_DEP
Definition: change_impact.cpp:231
irep_idt
dstringt irep_idt
Definition: irep.h:32
to_string
std::string to_string(const string_not_contains_constraintt &expr)
Used for debug printing.
Definition: string_constraint.cpp:55
impact_modet::BOTH
@ BOTH
change_impactt::old_goto_functions
const goto_functionst & old_goto_functions
Definition: change_impact.cpp:216
goto_functionst::function_map
function_mapt function_map
Definition: goto_functions.h:27
change_impactt::unified_diff
unified_difft unified_diff
Definition: change_impact.cpp:221
cfg_baset::entries
const entry_mapt & entries() const
Get a map from program points to their corresponding node indices.
Definition: cfg.h:259
change_impactt::change_impact
void change_impact(const irep_idt &function_id)
Definition: change_impact.cpp:315
unified_difft
Definition: unified_diff.h:31
full_slicert::queuet
std::stack< cfgt::entryt > queuet
Definition: full_slicer_class.h:64
full_slicert::cfg
cfgt cfg
Definition: full_slicer_class.h:61
change_impactt::output_change_impact
void output_change_impact(const irep_idt &function_id, const goto_program_change_impactt &c_i, const goto_functionst &goto_functions, const namespacet &ns) const
Definition: change_impact.cpp:558
change_impactt::mod_flagt
mod_flagt
Definition: change_impact.cpp:227
namespacet
A namespacet is essentially one or two symbol tables bound together, to allow for symbol lookups in t...
Definition: namespace.h:92
full_slicert::add_dependencies
void add_dependencies(const cfgt::nodet &node, queuet &queue, const dependence_grapht &dep_graph, const dep_node_to_cfgt &dep_node_to_cfg)
Definition: full_slicer.cpp:20
unified_diff.h
Unified diff (using LCSS) of goto functions.
change_impactt::propogate_dep_back
void propogate_dep_back(const irep_idt &function_id, const dependence_grapht::nodet &d_node, const dependence_grapht &dep_graph, goto_functions_change_impactt &change_impact, bool del)
Definition: change_impact.cpp:452
graph_nodet::in
edgest in
Definition: graph.h:43
change_impactt::goto_functions_change_impactt
std::map< irep_idt, goto_program_change_impactt > goto_functions_change_impactt
Definition: change_impact.cpp:240
cfg_baset::get_node
nodet & get_node(const goto_programt::const_targett &program_point)
Get the CFG graph node relating to program_point.
Definition: cfg.h:245
id2string
const std::string & id2string(const irep_idt &d)
Definition: irep.h:44
goto_programt::output_instruction
std::ostream & output_instruction(const namespacet &ns, const irep_idt &identifier, std::ostream &out, const instructionst::value_type &instruction) const
Output a single instruction.
Definition: goto_program.cpp:41
to_code_dead
const code_deadt & to_code_dead(const codet &code)
Definition: std_code.h:519
cfg_baset::get_node_index
entryt get_node_index(const goto_programt::const_targett &program_point) const
Get the graph node index for program_point.
Definition: cfg.h:239
change_impactt::NEW
@ NEW
Definition: change_impact.cpp:229
change_impactt::change_impactt
change_impactt(const goto_modelt &model_old, const goto_modelt &model_new, impact_modet impact_mode, bool compact_output)
Definition: change_impact.cpp:289
change_impactt::new_dep_graph
dependence_grapht new_dep_graph
Definition: change_impact.cpp:224
change_impactt::ns_new
const namespacet ns_new
Definition: change_impact.cpp:219
change_impactt::NEW_CTRL_DEP
@ NEW_CTRL_DEP
Definition: change_impact.cpp:233
code_deadt::symbol
symbol_exprt & symbol()
Definition: std_code.h:473
change_impactt::SAME
@ SAME
Definition: change_impact.cpp:228
change_impactt::old_dep_graph
dependence_grapht old_dep_graph
Definition: change_impact.cpp:223
dstringt::empty
bool empty() const
Definition: dstring.h:88
unified_difft::differencet::DELETED
@ DELETED
impact_modet::FORWARD
@ FORWARD
change_impactt::new_change_impact
goto_functions_change_impactt new_change_impact
Definition: change_impact.cpp:242
full_slicert::add_decl_dead
void add_decl_dead(const cfgt::nodet &node, queuet &queue, decl_deadt &decl_dead)
Definition: full_slicer.cpp:54
dep_edget::kindt::BOTH
@ BOTH
change_impactt::impact_mode
impact_modet impact_mode
Definition: change_impact.cpp:213
code_declt::symbol
symbol_exprt & symbol()
Definition: std_code.h:408
Forall_goto_functions
#define Forall_goto_functions(it, functions)
Definition: goto_functions.h:117
full_slicert::operator()
void operator()(goto_functionst &goto_functions, const namespacet &ns, const slicing_criteriont &criterion)
Definition: full_slicer.cpp:254
full_slicert::add_jumps
void add_jumps(queuet &queue, jumpst &jumps, const dependence_grapht::post_dominators_mapt &post_dominators)
Definition: full_slicer.cpp:85
change_impactt::DEL_CTRL_DEP
@ DEL_CTRL_DEP
Definition: change_impact.cpp:234
cfg_baset< cfg_nodet >
goto_programt::instructions
instructionst instructions
The list of instructions in the goto program.
Definition: goto_program.h:585
dep_edget::kindt::DATA
@ DATA
goto_functionst
A collection of goto functions.
Definition: goto_functions.h:23
cfg_baset< cfg_nodet >::nodet
base_grapht::nodet nodet
Definition: cfg.h:92
full_slicert::fixedpoint
void fixedpoint(goto_functionst &goto_functions, queuet &queue, jumpst &jumps, decl_deadt &decl_dead, const dependence_grapht &dep_graph)
Definition: full_slicer.cpp:190
unified_difft::differencet::NEW
@ NEW
change_impactt::DELETED
@ DELETED
Definition: change_impact.cpp:230
change_impactt
Definition: change_impact.cpp:202
goto_programt
A generic container class for the GOTO intermediate representation of one function.
Definition: goto_program.h:73
change_impact.h
Data and control-dependencies of syntactic diff.
unified_difft::get_diff
goto_program_difft get_diff(const irep_idt &function) const
Definition: unified_diff.cpp:31
change_impactt::compact_output
bool compact_output
Definition: change_impact.cpp:214
forall_goto_functions
#define forall_goto_functions(it, functions)
Definition: goto_functions.h:122
goto_programt::const_targett
instructionst::const_iterator const_targett
Definition: goto_program.h:580
full_slicert::jumpst
std::list< cfgt::entryt > jumpst
Definition: full_slicer_class.h:65
full_slicert::decl_deadt
std::unordered_map< irep_idt, queuet > decl_deadt
Definition: full_slicer_class.h:66
full_slicert::add_function_calls
void add_function_calls(const cfgt::nodet &node, queuet &queue, const goto_functionst &goto_functions)
Definition: full_slicer.cpp:36
implicit
static bool implicit(goto_programt::const_targett target)
Definition: full_slicer.cpp:234
dep_nodet
Definition: dependence_graph.h:59
change_impactt::DEL_DATA_DEP
@ DEL_DATA_DEP
Definition: change_impact.cpp:232
unified_difft::goto_program_difft
std::list< std::pair< goto_programt::const_targett, differencet > > goto_program_difft
Definition: unified_diff.h:47
full_slicert::add_to_queue
void add_to_queue(queuet &queue, const cfgt::entryt &entry, goto_programt::const_targett reason)
Definition: full_slicer_class.h:96
forall_goto_program_instructions
#define forall_goto_program_instructions(it, program)
Definition: goto_program.h:1196
dependence_graph.h
Field-Sensitive Program Dependence Analysis, Litvak et al., FSE 2010.
grapht< dep_nodet >::nodet
dep_nodet nodet
Definition: graph.h:170