cprover
dependence_graph.cpp
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Field-Sensitive Program Dependence Analysis, Litvak et al.,
4  FSE 2010
5 
6 Author: Michael Tautschnig
7 
8 Date: August 2013
9 
10 \*******************************************************************/
11 
14 
15 #include "dependence_graph.h"
16 
17 #include <util/container_utils.h>
18 #include <util/json_irep.h>
19 
20 #include "goto_rw.h"
21 
23  const dep_graph_domaint &src,
24  trace_ptrt,
25  trace_ptrt)
26 {
27  // An abstract state at location `to` may be non-bottom even if
28  // `merge(..., `to`) has not been called so far. This is due to the special
29  // handling of function entry edges (see transform()).
30  bool changed = is_bottom() || has_changed;
31 
32  // For computing the data dependencies, we would not need a fixpoint
33  // computation. The data dependencies at a location are computed from the
34  // result of the reaching definitions analysis at that location
35  // (in data_dependencies()). Thus, we only need to set the data dependencies
36  // part of an abstract state at a certain location once.
37  if(changed && data_deps.empty())
38  {
39  data_deps = src.data_deps;
41  }
42 
44  changed |=
46 
47  has_changed = false;
48 
49  return changed;
50 }
51 
53  const irep_idt &function_id,
56  dependence_grapht &dep_graph)
57 {
58  // Better Slicing of Programs with Jumps and Switches
59  // Kumar and Horwitz, FASE'02:
60  // "Node N is control dependent on node M iff N postdominates, in
61  // the CFG, one but not all of M's CFG successors."
62  //
63  // The "successor" above refers to an immediate successor of M.
64  //
65  // When computing the control dependencies of a node N (i.e., "to"
66  // being N), candidates for M are all control statements (gotos or
67  // assumes) from which there is a path in the CFG to N.
68 
69  // Add new candidates
70 
71  if(from->is_goto() || from->is_assume())
72  control_dep_candidates.insert(from);
73  else if(from->is_end_function())
74  {
75  control_dep_candidates.clear();
76  return;
77  }
78 
79  if(control_dep_candidates.empty())
80  return;
81 
82  // Get postdominators
83 
84  const irep_idt id = function_id;
85  const cfg_post_dominatorst &pd=dep_graph.cfg_post_dominators().at(id);
86 
87  // Check all candidates
88 
89  for(const auto &control_dep_candidate : control_dep_candidates)
90  {
91  // check all CFG successors of M
92  // special case: assumptions also introduce a control dependency
93  bool post_dom_all = !control_dep_candidate->is_assume();
94  bool post_dom_one=false;
95 
96  // we could hard-code assume and goto handling here to improve
97  // performance
99  pd.get_node(control_dep_candidate);
100 
101  // successors of M
102  for(const auto &edge : m.out)
103  {
104  // Could use pd.dominates(to, control_dep_candidate) but this would impose
105  // another dominator node lookup per call to this function, which is too
106  // expensive.
108  pd.cfg[edge.first];
109 
110  if(m_s.dominators.find(to)!=m_s.dominators.end())
111  post_dom_one=true;
112  else
113  post_dom_all=false;
114  }
115 
116  if(post_dom_all || !post_dom_one)
117  {
118  control_deps.erase(control_dep_candidate);
119  }
120  else
121  {
122  control_deps.insert(control_dep_candidate);
123  }
124  }
125 }
126 
128  const mp_integer &w_start,
129  const mp_integer &w_end,
130  const mp_integer &r_start,
131  const mp_integer &r_end)
132 {
133  assert(w_start>=0);
134  assert(r_start>=0);
135 
136  if((w_end!=-1 && w_end <= r_start) || // we < rs
137  (r_end!=-1 && w_start >= r_end)) // re < we
138  return false;
139  else if(w_start >= r_start) // rs <= ws < we,re
140  return true;
141  else if(w_end==-1 ||
142  (r_end!=-1 && w_end > r_start)) // ws <= rs < we,re
143  return true;
144  else
145  return false;
146 }
147 
150  const irep_idt &function_to,
152  dependence_grapht &dep_graph,
153  const namespacet &ns)
154 {
155  // data dependencies using def-use pairs
156  data_deps.clear();
157 
158  // TODO use (future) reaching-definitions-dereferencing rw_set
159  value_setst &value_sets=
160  dep_graph.reaching_definitions().get_value_sets();
161  rw_range_set_value_sett rw_set(ns, value_sets);
162  goto_rw(function_to, to, rw_set);
163 
164  for(const auto &read_object_entry : rw_set.get_r_set())
165  {
166  const range_domaint &r_ranges = rw_set.get_ranges(read_object_entry.second);
167  const rd_range_domaint::ranges_at_loct &w_ranges =
168  dep_graph.reaching_definitions()[to].get(read_object_entry.first);
169 
170  for(const auto &w_range : w_ranges)
171  {
172  bool found=false;
173  for(const auto &wr : w_range.second)
174  {
175  for(const auto &r_range : r_ranges)
176  {
177  if(!found &&
178  may_be_def_use_pair(wr.first, wr.second,
179  r_range.first, r_range.second))
180  {
181  // found a def-use pair
182  data_deps.insert(w_range.first);
183  found=true;
184  }
185  }
186  }
187  }
188 
189  dep_graph.reaching_definitions()[to].clear_cache(read_object_entry.first);
190  }
191 }
192 
194  const irep_idt &function_from,
195  trace_ptrt trace_from,
196  const irep_idt &function_to,
197  trace_ptrt trace_to,
198  ai_baset &ai,
199  const namespacet &ns)
200 {
201  locationt from{trace_from->current_location()};
202  locationt to{trace_to->current_location()};
203 
204  dependence_grapht *dep_graph=dynamic_cast<dependence_grapht*>(&ai);
205  assert(dep_graph!=nullptr);
206 
207  // We do not propagate control dependencies on function calls, i.e., only the
208  // entry point of a function should have a control dependency on the call
209  if(!control_deps.empty())
210  {
211  const goto_programt::const_targett &dep = *control_deps.begin();
212  if(dep->is_function_call())
213  {
214  INVARIANT(
215  std::all_of(
216  std::next(control_deps.begin()),
217  control_deps.end(),
218  [](const goto_programt::const_targett &d) {
219  return d->is_function_call();
220  }),
221  "All entries must be function calls");
222 
223  control_deps.clear();
224  }
225  }
226 
227  // propagate control dependencies across function calls
228  if(from->is_function_call())
229  {
230  if(function_from == function_to)
231  {
232  control_dependencies(function_from, from, to, *dep_graph);
233  }
234  else
235  {
236  // edge to function entry point
237  const goto_programt::const_targett next = std::next(from);
238 
240  dynamic_cast<dep_graph_domaint*>(&(dep_graph->get_state(next)));
241  assert(s!=nullptr);
242 
243  if(s->is_bottom())
244  {
245  s->has_values = tvt::unknown();
246  s->has_changed = true;
247  }
248 
252 
253  control_deps.clear();
254  control_deps.insert(from);
255 
256  control_dep_candidates.clear();
257  }
258  }
259  else
260  control_dependencies(function_from, from, to, *dep_graph);
261 
262  data_dependencies(from, function_to, to, *dep_graph, ns);
263 }
264 
266  std::ostream &out,
267  const ai_baset &,
268  const namespacet &) const
269 {
270  if(!control_deps.empty())
271  {
272  out << "Control dependencies: ";
273  for(depst::const_iterator
274  it=control_deps.begin();
275  it!=control_deps.end();
276  ++it)
277  {
278  if(it!=control_deps.begin())
279  out << ",";
280  out << (*it)->location_number;
281  }
282  out << '\n';
283  }
284 
285  if(!data_deps.empty())
286  {
287  out << "Data dependencies: ";
288  for(depst::const_iterator
289  it=data_deps.begin();
290  it!=data_deps.end();
291  ++it)
292  {
293  if(it!=data_deps.begin())
294  out << ",";
295  out << (*it)->location_number;
296  }
297  out << '\n';
298  }
299 }
300 
305  const ai_baset &,
306  const namespacet &) const
307 {
308  json_arrayt graph;
309 
310  for(const auto &cd : control_deps)
311  {
312  json_objectt link{
313  {"locationNumber", json_numbert(std::to_string(cd->location_number))},
314  {"sourceLocation", json(cd->source_location)},
315  {"type", json_stringt("control")}};
316  graph.push_back(std::move(link));
317  }
318 
319  for(const auto &dd : data_deps)
320  {
321  json_objectt link{
322  {"locationNumber", json_numbert(std::to_string(dd->location_number))},
323  {"sourceLocation", json(dd->source_location)},
324  {"type", json_stringt("data")}};
325  graph.push_back(std::move(link));
326  }
327 
328  return std::move(graph);
329 }
330 
334 class dep_graph_domain_factoryt : public ai_domain_factoryt<dep_graph_domaint>
335 {
336 public:
338  {
339  }
340 
341  std::unique_ptr<statet> make(locationt l) const override
342  {
343  auto node_id = dg.add_node();
344  dg.nodes[node_id].PC = l;
345  auto p = util_make_unique<dep_graph_domaint>(node_id);
346  CHECK_RETURN(p->is_bottom());
347 
348  return std::unique_ptr<statet>(p.release());
349  }
350 
351 private:
353 };
354 
357  ns(_ns),
358  rd(ns)
359 {
360 }
361 
363  dep_edget::kindt kind,
366 {
367  const node_indext n_from = (*this)[from].get_node_id();
368  assert(n_from<size());
369  const node_indext n_to = (*this)[to].get_node_id();
370  assert(n_to<size());
371 
372  // add_edge is redundant as the subsequent operations also insert
373  // entries into the edge maps (implicitly)
374  // add_edge(n_from, n_to);
375  nodes[n_from].out[n_to].add(kind);
376  nodes[n_to].in[n_from].add(kind);
377 }
378 
380  dependence_grapht &dep_graph, goto_programt::const_targett this_loc) const
381 {
382  for(const auto &c_dep : control_deps)
383  dep_graph.add_dep(dep_edget::kindt::CTRL, c_dep, this_loc);
384 
385  for(const auto &d_dep : data_deps)
386  dep_graph.add_dep(dep_edget::kindt::DATA, d_dep, this_loc);
387 }
dependence_grapht::reaching_definitions
const reaching_definitions_analysist & reaching_definitions() const
Definition: dependence_graph.h:264
dstringt
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:37
rw_range_sett::get_r_set
const objectst & get_r_set() const
Definition: goto_rw.h:115
json_numbert
Definition: json.h:291
grapht< dep_nodet >::size
std::size_t size() const
Definition: graph.h:212
dep_graph_domaint::data_deps
depst data_deps
Definition: dependence_graph.h:188
mp_integer
BigInt mp_integer
Definition: smt_terms.h:12
dep_graph_domaint::transform
void transform(const irep_idt &function_from, trace_ptrt trace_from, const irep_idt &function_to, trace_ptrt trace_to, ai_baset &ai, const namespacet &ns) final override
how function calls are treated: a) there is an edge from each call site to the function head b) there...
Definition: dependence_graph.cpp:193
dep_graph_domaint::has_changed
bool has_changed
Definition: dependence_graph.h:173
dependence_grapht
Definition: dependence_graph.h:214
dependence_grapht::add_dep
void add_dep(dep_edget::kindt kind, goto_programt::const_targett from, goto_programt::const_targett to)
Definition: dependence_graph.cpp:362
dependence_grapht::dependence_grapht
dependence_grapht(const namespacet &_ns)
Definition: dependence_graph.cpp:355
CHECK_RETURN
#define CHECK_RETURN(CONDITION)
Definition: invariant.h:495
reaching_definitions_analysist::get_value_sets
value_setst & get_value_sets() const
Definition: reaching_definitions.h:344
rw_range_sett::get_ranges
const range_domaint & get_ranges(const std::unique_ptr< range_domain_baset > &ranges) const
Definition: goto_rw.h:126
dependence_grapht::cfg_post_dominators
const post_dominators_mapt & cfg_post_dominators() const
Definition: dependence_graph.h:259
goto_rw
static void goto_rw(const irep_idt &function, goto_programt::const_targett target, const code_assignt &assign, rw_range_sett &rw_set)
Definition: goto_rw.cpp:720
grapht::add_node
node_indext add_node(arguments &&... values)
Definition: graph.h:180
ait
ait supplies three of the four components needed: an abstract interpreter (in this case handling func...
Definition: ai.h:564
rd_range_domaint::ranges_at_loct
std::map< locationt, rangest > ranges_at_loct
Definition: reaching_definitions.h:230
dep_graph_domaint::is_bottom
bool is_bottom() const final override
Definition: dependence_graph.h:147
to_string
std::string to_string(const string_not_contains_constraintt &expr)
Used for debug printing.
Definition: string_constraint.cpp:57
rw_range_set_value_sett
Definition: goto_rw.h:258
jsont
Definition: json.h:27
dep_graph_domain_factoryt
This ensures that all domains are constructed with the node ID that links them to the graph part of t...
Definition: dependence_graph.cpp:335
json_irep.h
Util.
dep_graph_domaint::output
void output(std::ostream &out, const ai_baset &ai, const namespacet &ns) const final override
Definition: dependence_graph.cpp:265
ai_domain_baset::trace_ptrt
ai_history_baset::trace_ptrt trace_ptrt
Definition: ai_domain.h:74
goto_rw.h
json_arrayt
Definition: json.h:165
grapht< dep_nodet >::node_indext
nodet::node_indext node_indext
Definition: graph.h:173
json_objectt
Definition: json.h:300
dep_graph_domaint::has_values
tvt has_values
Definition: dependence_graph.h:171
namespacet
A namespacet is essentially one or two symbol tables bound together, to allow for symbol lookups in t...
Definition: namespace.h:91
util_make_unique
std::unique_ptr< T > util_make_unique(Ts &&... ts)
Definition: make_unique.h:19
dep_graph_domain_factoryt::dep_graph_domain_factoryt
dep_graph_domain_factoryt(dependence_grapht &_dg)
Definition: dependence_graph.cpp:337
dep_graph_domaint::control_dependencies
void control_dependencies(const irep_idt &function_id, goto_programt::const_targett from, goto_programt::const_targett to, dependence_grapht &dep_graph)
Definition: dependence_graph.cpp:52
dep_graph_domain_factoryt::make
std::unique_ptr< statet > make(locationt l) const override
Definition: dependence_graph.cpp:341
util_inplace_set_union
bool util_inplace_set_union(std::set< T, Compare, Alloc > &target, const std::set< T, Compare, Alloc > &source)
Compute union of two sets.
Definition: container_utils.h:28
json
static void json(json_objectT &result, const irep_idt &property_id, const property_infot &property_info)
Definition: properties.cpp:116
dep_edget::kindt
kindt
Definition: dependence_graph.h:30
cfg_dominators_templatet::nodet::dominators
target_sett dominators
Definition: cfg_dominators.h:43
dep_graph_domain_factoryt::dg
dependence_grapht & dg
Definition: dependence_graph.cpp:352
cfg_dominators_templatet::get_node
const cfgt::nodet & get_node(const T &program_point) const
Get the graph node (which gives dominators, predecessors and successors) for program_point.
Definition: cfg_dominators.h:53
may_be_def_use_pair
static bool may_be_def_use_pair(const mp_integer &w_start, const mp_integer &w_end, const mp_integer &r_start, const mp_integer &r_end)
Definition: dependence_graph.cpp:127
grapht::nodes
nodest nodes
Definition: graph.h:176
tvt::unknown
static tvt unknown()
Definition: threeval.h:33
dep_graph_domaint::control_dep_candidates
depst control_dep_candidates
Definition: dependence_graph.h:184
dep_graph_domaint::control_deps
depst control_deps
Definition: dependence_graph.h:179
dep_edget::kindt::DATA
@ DATA
ai_domain_baset::locationt
goto_programt::const_targett locationt
Definition: ai_domain.h:73
ai_domain_factoryt
Definition: ai_domain.h:197
dep_graph_domaint::merge
bool merge(const dep_graph_domaint &src, trace_ptrt from, trace_ptrt to)
Definition: dependence_graph.cpp:22
value_setst
Definition: value_sets.h:22
dep_edget::kindt::CTRL
@ CTRL
container_utils.h
dep_graph_domaint::data_dependencies
void data_dependencies(goto_programt::const_targett from, const irep_idt &function_to, goto_programt::const_targett to, dependence_grapht &dep_graph, const namespacet &ns)
Definition: dependence_graph.cpp:148
ai_baset
This is the basic interface of the abstract interpreter with default implementations of the core func...
Definition: ai.h:119
ai_domain_factory_baset::locationt
ai_domain_baset::locationt locationt
Definition: ai_domain.h:171
goto_programt::const_targett
instructionst::const_iterator const_targett
Definition: goto_program.h:647
dep_graph_domaint::populate_dep_graph
void populate_dep_graph(dependence_grapht &, goto_programt::const_targett) const
Definition: dependence_graph.cpp:379
cfg_dominators_templatet::nodet
Definition: cfg_dominators.h:42
INVARIANT
#define INVARIANT(CONDITION, REASON)
This macro uses the wrapper function 'invariant_violated_string'.
Definition: invariant.h:423
ait::get_state
virtual statet & get_state(locationt l)
Definition: ai.h:613
sparse_bitvector_analysist::get
const V & get(const std::size_t value_index) const
Definition: reaching_definitions.h:45
dep_graph_domaint::output_json
jsont output_json(const ai_baset &ai, const namespacet &ns) const override
Outputs the current value of the domain.
Definition: dependence_graph.cpp:304
cfg_dominators_templatet::cfg
cfgt cfg
Definition: cfg_dominators.h:47
dep_graph_domaint
Definition: dependence_graph.h:67
json_arrayt::push_back
jsont & push_back(const jsont &json)
Definition: json.h:212
dependence_graph.h
Field-Sensitive Program Dependence Analysis, Litvak et al., FSE 2010.
cfg_dominators_templatet
Dominator graph.
Definition: cfg_dominators.h:37
json_stringt
Definition: json.h:270
range_domaint
Definition: goto_rw.h:70