cprover
cfg_dominators.h
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Compute dominators for CFG of goto_function
4 
5 Author: Georg Weissenbacher, georg@weissenbacher.name
6 
7 \*******************************************************************/
8 
11 
12 #ifndef CPROVER_ANALYSES_CFG_DOMINATORS_H
13 #define CPROVER_ANALYSES_CFG_DOMINATORS_H
14 
15 #include <set>
16 #include <list>
17 #include <map>
18 #include <iosfwd>
19 
22 #include <goto-programs/cfg.h>
23 
35 template <class P, class T, bool post_dom>
37 {
38 public:
39  typedef std::set<T> target_sett;
40 
41  struct nodet
42  {
44  };
45 
48 
49  void operator()(P &program);
50 
53  const typename cfgt::nodet &get_node(const T &program_point) const
54  {
55  return cfg.get_node(program_point);
56  }
57 
60  typename cfgt::nodet &get_node(const T &program_point)
61  {
62  return cfg.get_node(program_point);
63  }
64 
66  typename cfgt::entryt get_node_index(const T &program_point) const
67  {
68  return cfg.get_node_index(program_point);
69  }
70 
76  bool dominates(T lhs, const nodet &rhs_node) const
77  {
78  return rhs_node.dominators.count(lhs);
79  }
80 
83  bool dominates(T lhs, T rhs) const
84  {
85  return dominates(lhs, get_node(rhs));
86  }
87 
91  bool program_point_reachable(const nodet &program_point_node) const
92  {
93  // Dominator analysis walks from the entry point, so a side-effect is to
94  // identify unreachable program points (those which don't dominate even
95  // themselves).
96  return !program_point_node.dominators.empty();
97  }
98 
102  bool program_point_reachable(T program_point) const
103  {
104  // Dominator analysis walks from the entry point, so a side-effect is to
105  // identify unreachable program points (those which don't dominate even
106  // themselves).
107  return program_point_reachable(get_node(program_point));
108  }
109 
111 
112  void output(std::ostream &) const;
113 
114 protected:
115  void initialise(P &program);
116  void fixedpoint(P &program);
117 };
118 
120 template <class P, class T, bool post_dom>
121 std::ostream &operator << (
122  std::ostream &out,
123  const cfg_dominators_templatet<P, T, post_dom> &cfg_dominators)
124 {
125  cfg_dominators.output(out);
126  return out;
127 }
128 
130 template <class P, class T, bool post_dom>
132 {
133  initialise(program);
134  fixedpoint(program);
135 }
136 
138 template <class P, class T, bool post_dom>
140 {
141  cfg(program);
142 }
143 
145 template <class P, class T, bool post_dom>
147 {
148  std::list<T> worklist;
149 
150  if(cfgt::nodes_empty(program))
151  return;
152 
153  if(post_dom)
154  entry_node = cfgt::get_last_node(program);
155  else
156  entry_node = cfgt::get_first_node(program);
157  typename cfgt::nodet &n = cfg.get_node(entry_node);
158  n.dominators.insert(entry_node);
159 
160  for(typename cfgt::edgest::const_iterator
161  s_it=(post_dom?n.in:n.out).begin();
162  s_it!=(post_dom?n.in:n.out).end();
163  ++s_it)
164  worklist.push_back(cfg[s_it->first].PC);
165 
166  while(!worklist.empty())
167  {
168  // get node from worklist
169  T current=worklist.front();
170  worklist.pop_front();
171 
172  bool changed=false;
173  typename cfgt::nodet &node = cfg.get_node(current);
174  if(node.dominators.empty())
175  {
176  for(const auto &edge : (post_dom ? node.out : node.in))
177  if(!cfg[edge.first].dominators.empty())
178  {
179  node.dominators=cfg[edge.first].dominators;
180  node.dominators.insert(current);
181  changed=true;
182  }
183  }
184 
185  // compute intersection of predecessors
186  for(const auto &edge : (post_dom ? node.out : node.in))
187  {
188  const target_sett &other=cfg[edge.first].dominators;
189  if(other.empty())
190  continue;
191 
192  typename target_sett::const_iterator n_it=node.dominators.begin();
193  typename target_sett::const_iterator o_it=other.begin();
194 
195  // in-place intersection. not safe to use set_intersect
196  while(n_it!=node.dominators.end() && o_it!=other.end())
197  {
198  if(*n_it==current)
199  ++n_it;
200  else if(*n_it<*o_it)
201  {
202  changed=true;
203  node.dominators.erase(n_it++);
204  }
205  else if(*o_it<*n_it)
206  ++o_it;
207  else
208  {
209  ++n_it;
210  ++o_it;
211  }
212  }
213 
214  while(n_it!=node.dominators.end())
215  {
216  if(*n_it==current)
217  ++n_it;
218  else
219  {
220  changed=true;
221  node.dominators.erase(n_it++);
222  }
223  }
224  }
225 
226  if(changed) // fixed point for node reached?
227  {
228  for(const auto &edge : (post_dom ? node.in : node.out))
229  {
230  worklist.push_back(cfg[edge.first].PC);
231  }
232  }
233  }
234 }
235 
239 template <class T>
240 void dominators_pretty_print_node(const T &node, std::ostream &out)
241 {
242  out << node;
243 }
244 
246  const goto_programt::targett& target,
247  std::ostream& out)
248 {
249  out << target->code.pretty();
250 }
251 
253 template <class P, class T, bool post_dom>
255 {
256  for(const auto &node : cfg.entries())
257  {
258  auto n=node.first;
259 
261  if(post_dom)
262  out << " post-dominated by ";
263  else
264  out << " dominated by ";
265  bool first=true;
266  for(const auto &d : cfg[node.second].dominators)
267  {
268  if(!first)
269  out << ", ";
270  first=false;
272  }
273  out << "\n";
274  }
275 }
276 
280 
284 
285 template<>
287  const goto_programt::const_targett &node,
288  std::ostream &out)
289 {
290  out << node->location_number;
291 }
292 
293 #endif // CPROVER_ANALYSES_CFG_DOMINATORS_H
Control Flow Graph.
cfg_dominators_templatet< const goto_programt, goto_programt::const_targett, false > cfg_dominatorst
void dominators_pretty_print_node(const T &node, std::ostream &out)
Pretty-print a single node in the dominator tree.
std::ostream & operator<<(std::ostream &out, const cfg_dominators_templatet< P, T, post_dom > &cfg_dominators)
Print the result of the dominator computation.
cfg_dominators_templatet< const goto_programt, goto_programt::const_targett, true > cfg_post_dominatorst
base_grapht::node_indext entryt
Definition: cfg.h:91
entryt get_node_index(const goto_programt::const_targett &program_point) const
Get the graph node index for program_point.
Definition: cfg.h:239
nodet & get_node(const goto_programt::const_targett &program_point)
Get the CFG graph node relating to program_point.
Definition: cfg.h:245
bool dominates(T lhs, T rhs) const
Returns true if program point lhs dominates rhs.
procedure_local_cfg_baset< nodet, P, T > cfgt
cfgt::nodet & get_node(const T &program_point)
Get the graph node (which gives dominators, predecessors and successors) for program_point.
void output(std::ostream &) const
Print the result of the dominator computation.
void operator()(P &program)
Compute dominators.
bool dominates(T lhs, const nodet &rhs_node) const
Returns true if the program point corresponding to rhs_node is dominated by program point lhs.
void fixedpoint(P &program)
Computes the MOP for the dominator analysis.
bool program_point_reachable(const nodet &program_point_node) const
Returns true if the program point for program_point_node is reachable from the entry point.
bool program_point_reachable(T program_point) const
Returns true if the program point for program_point_node is reachable from the entry point.
const cfgt::nodet & get_node(const T &program_point) const
Get the graph node (which gives dominators, predecessors and successors) for program_point.
void initialise(P &program)
Initialises the elements of the fixed point analysis.
cfgt::entryt get_node_index(const T &program_point) const
Get the graph node index for program_point.
A generic container class for the GOTO intermediate representation of one function.
Definition: goto_program.h:74
instructionst::iterator targett
Definition: goto_program.h:550
instructionst::const_iterator const_targett
Definition: goto_program.h:551
edgest in
Definition: graph.h:42
edgest out
Definition: graph.h:42
Goto Programs with Functions.
Concrete Goto Program.