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 <cassert>
18 
19 #include <util/container_utils.h>
20 #include <util/json.h>
21 #include <util/json_expr.h>
22 
23 #include "goto_rw.h"
24 
26  const dep_graph_domaint &src,
29 {
30  // An abstract state at location `to` may be non-bottom even if
31  // `merge(..., `to`) has not been called so far. This is due to the special
32  // handling of function entry edges (see transform()).
33  bool changed = is_bottom() || has_changed;
34 
35  // For computing the data dependencies, we would not need a fixpoint
36  // computation. The data dependencies at a location are computed from the
37  // result of the reaching definitions analysis at that location
38  // (in data_dependencies()). Thus, we only need to set the data dependencies
39  // part of an abstract state at a certain location once.
40  if(changed && data_deps.empty())
41  {
42  data_deps = src.data_deps;
44  }
45 
47  changed |=
49 
50  has_changed = false;
51 
52  return changed;
53 }
54 
58  dependence_grapht &dep_graph)
59 {
60  // Better Slicing of Programs with Jumps and Switches
61  // Kumar and Horwitz, FASE'02:
62  // "Node N is control dependent on node M iff N postdominates, in
63  // the CFG, one but not all of M's CFG successors."
64  //
65  // The "successor" above refers to an immediate successor of M.
66  //
67  // When computing the control dependencies of a node N (i.e., "to"
68  // being N), candidates for M are all control statements (gotos or
69  // assumes) from which there is a path in the CFG to N.
70 
71  // Add new candidates
72 
73  if(from->is_goto() || from->is_assume())
74  control_dep_candidates.insert(from);
75  else if(from->is_end_function())
76  {
77  control_dep_candidates.clear();
78  return;
79  }
80 
81  if(control_dep_candidates.empty())
82  return;
83 
84  // Get postdominators
85 
86  const irep_idt id=from->function;
87  const cfg_post_dominatorst &pd=dep_graph.cfg_post_dominators().at(id);
88 
89  // Check all candidates
90 
91  for(const auto &control_dep_candidate : control_dep_candidates)
92  {
93  // check all CFG successors of M
94  // special case: assumptions also introduce a control dependency
95  bool post_dom_all = !control_dep_candidate->is_assume();
96  bool post_dom_one=false;
97 
98  // we could hard-code assume and goto handling here to improve
99  // performance
100  cfg_post_dominatorst::cfgt::entry_mapt::const_iterator e =
101  pd.cfg.entry_map.find(control_dep_candidate);
102 
103  INVARIANT(
104  e != pd.cfg.entry_map.end(), "cfg must have an entry for every location");
105 
107  pd.cfg[e->second];
108 
109  // successors of M
110  for(const auto &edge : m.out)
111  {
113  pd.cfg[edge.first];
114 
115  if(m_s.dominators.find(to)!=m_s.dominators.end())
116  post_dom_one=true;
117  else
118  post_dom_all=false;
119  }
120 
121  if(post_dom_all || !post_dom_one)
122  {
123  control_deps.erase(control_dep_candidate);
124  }
125  else
126  {
127  control_deps.insert(control_dep_candidate);
128  }
129  }
130 }
131 
133  const mp_integer &w_start,
134  const mp_integer &w_end,
135  const mp_integer &r_start,
136  const mp_integer &r_end)
137 {
138  assert(w_start>=0);
139  assert(r_start>=0);
140 
141  if((w_end!=-1 && w_end <= r_start) || // we < rs
142  (r_end!=-1 && w_start >= r_end)) // re < we
143  return false;
144  else if(w_start >= r_start) // rs <= ws < we,re
145  return true;
146  else if(w_end==-1 ||
147  (r_end!=-1 && w_end > r_start)) // ws <= rs < we,re
148  return true;
149  else
150  return false;
151 }
152 
156  dependence_grapht &dep_graph,
157  const namespacet &ns)
158 {
159  // data dependencies using def-use pairs
160  data_deps.clear();
161 
162  // TODO use (future) reaching-definitions-dereferencing rw_set
163  value_setst &value_sets=
164  dep_graph.reaching_definitions().get_value_sets();
165  rw_range_set_value_sett rw_set(ns, value_sets);
166  goto_rw(to, rw_set);
167 
169  {
170  const range_domaint &r_ranges=rw_set.get_ranges(it);
171  const rd_range_domaint::ranges_at_loct &w_ranges=
172  dep_graph.reaching_definitions()[to].get(it->first);
173 
174  for(const auto &w_range : w_ranges)
175  {
176  bool found=false;
177  for(const auto &wr : w_range.second)
178  for(const auto &r_range : r_ranges)
179  if(!found &&
180  may_be_def_use_pair(wr.first, wr.second,
181  r_range.first, r_range.second))
182  {
183  // found a def-use pair
184  data_deps.insert(w_range.first);
185  found=true;
186  }
187  }
188 
189  dep_graph.reaching_definitions()[to].clear_cache(it->first);
190  }
191 }
192 
196  ai_baset &ai,
197  const namespacet &ns)
198 {
199  dependence_grapht *dep_graph=dynamic_cast<dependence_grapht*>(&ai);
200  assert(dep_graph!=nullptr);
201 
202  // propagate control dependencies across function calls
203  if(from->is_function_call())
204  {
205  if(from->function == to->function)
206  {
207  control_dependencies(from, to, *dep_graph);
208  }
209  else
210  {
211  // edge to function entry point
212  const goto_programt::const_targett next = std::next(from);
213 
215  dynamic_cast<dep_graph_domaint*>(&(dep_graph->get_state(next)));
216  assert(s!=nullptr);
217 
218  if(s->is_bottom())
219  {
220  s->has_values = tvt::unknown();
221  s->has_changed = true;
222  }
223 
227 
228  control_deps.clear();
229  control_dep_candidates.clear();
230  }
231  }
232  else
233  control_dependencies(from, to, *dep_graph);
234 
235  data_dependencies(from, to, *dep_graph, ns);
236 }
237 
239  std::ostream &out,
240  const ai_baset &,
241  const namespacet &) const
242 {
243  if(!control_deps.empty())
244  {
245  out << "Control dependencies: ";
246  for(depst::const_iterator
247  it=control_deps.begin();
248  it!=control_deps.end();
249  ++it)
250  {
251  if(it!=control_deps.begin())
252  out << ",";
253  out << (*it)->location_number;
254  }
255  out << '\n';
256  }
257 
258  if(!data_deps.empty())
259  {
260  out << "Data dependencies: ";
261  for(depst::const_iterator
262  it=data_deps.begin();
263  it!=data_deps.end();
264  ++it)
265  {
266  if(it!=data_deps.begin())
267  out << ",";
268  out << (*it)->location_number;
269  }
270  out << '\n';
271  }
272 }
273 
278  const ai_baset &,
279  const namespacet &) const
280 {
281  json_arrayt graph;
282 
283  for(const auto &cd : control_deps)
284  {
285  json_objectt &link=graph.push_back().make_object();
286  link["locationNumber"]=
287  json_numbert(std::to_string(cd->location_number));
288  link["sourceLocation"]=json(cd->source_location);
289  link["type"]=json_stringt("control");
290  }
291 
292  for(const auto &dd : data_deps)
293  {
294  json_objectt &link=graph.push_back().make_object();
295  link["locationNumber"]=
296  json_numbert(std::to_string(dd->location_number));
297  link["sourceLocation"]=json(dd->source_location);
298  json_stringt(dd->source_location.as_string());
299  link["type"]=json_stringt("data");
300  }
301 
302  return graph;
303 }
304 
306  dep_edget::kindt kind,
309 {
310  const node_indext n_from = (*this)[from].get_node_id();
311  assert(n_from<size());
312  const node_indext n_to = (*this)[to].get_node_id();
313  assert(n_to<size());
314 
315  // add_edge is redundant as the subsequent operations also insert
316  // entries into the edge maps (implicitly)
317  // add_edge(n_from, n_to);
318  nodes[n_from].out[n_to].add(kind);
319  nodes[n_to].in[n_from].add(kind);
320 }
321 
323  dependence_grapht &dep_graph, goto_programt::const_targett this_loc) const
324 {
325  for(const auto &c_dep : control_deps)
326  dep_graph.add_dep(dep_edget::kindt::CTRL, c_dep, this_loc);
327 
328  for(const auto &d_dep : data_deps)
329  dep_graph.add_dep(dep_edget::kindt::DATA, d_dep, this_loc);
330 }
void transform(goto_programt::const_targett from, goto_programt::const_targett 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...
void output(std::ostream &out, const ai_baset &ai, const namespacet &ns) const final override
BigInt mp_integer
Definition: mp_arith.h:22
Field-Sensitive Program Dependence Analysis, Litvak et al., FSE 2010.
entry_mapt entry_map
Definition: cfg.h:106
Definition: json.h:23
static tvt unknown()
Definition: threeval.h:33
bool util_inplace_set_union(std::set< T, Compare, Alloc > &target, const std::set< T, Compare, Alloc > &source)
Compute union of two sets.
const reaching_definitions_analysist & reaching_definitions() const
#define INVARIANT(CONDITION, REASON)
Definition: invariant.h:204
void add_dep(dep_edget::kindt kind, goto_programt::const_targett from, goto_programt::const_targett to)
jsont & push_back(const jsont &json)
Definition: json.h:163
void control_dependencies(goto_programt::const_targett from, goto_programt::const_targett to, dependence_grapht &dep_graph)
Expressions in JSON.
instructionst::const_iterator const_targett
Definition: goto_program.h:398
TO_BE_DOCUMENTED.
Definition: namespace.h:74
void goto_rw(goto_programt::const_targett target, const code_assignt &assign, rw_range_sett &rw_set)
Definition: goto_rw.cpp:688
jsont output_json(const ai_baset &ai, const namespacet &ns) const override
Outputs the current value of the domain.
const post_dominators_mapt & cfg_post_dominators() const
value_setst & get_value_sets() const
void populate_dep_graph(dependence_grapht &, goto_programt::const_targett) const
std::size_t size() const
Definition: graph.h:178
nodet::node_indext node_indext
Definition: graph.h:140
dstringt has one field, an unsigned integer no which is an index into a static table of strings...
Definition: dstring.h:33
#define forall_rw_range_set_r_objects(it, rw_set)
Definition: goto_rw.h:24
void data_dependencies(goto_programt::const_targett from, goto_programt::const_targett to, dependence_grapht &dep_graph, const namespacet &ns)
const V & get(const std::size_t value_index) const
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)
The basic interface of an abstract interpreter.
Definition: ai.h:32
bool merge(const dep_graph_domaint &src, goto_programt::const_targett from, goto_programt::const_targett to)
std::string to_string(const string_constraintt &expr)
Used for debug printing.
bool is_bottom() const final override
const range_domaint & get_ranges(objectst::const_iterator it) const
Definition: goto_rw.h:135
json_objectt & make_object()
Definition: json.h:290
virtual statet & get_state(goto_programt::const_targett l)
std::map< locationt, rangest > ranges_at_loct
json_objectt json(const source_locationt &location)
Definition: json_expr.cpp:83