ROSE  0.9.9.109
boostGraphCFG.h
1 #pragma once
2 
3 
4 // DQ (10/5/2014): This is more strict now that we include rose_config.h in the sage3basic.h.
5 // #include "rose.h"
6 // rose.h and sage3basic.h should not be included in librose header files. [Robb P. Matzke 2014-10-15]
7 // #include "sage3basic.h"
8 
9 #include <boost/graph/adjacency_list.hpp>
10 #include <boost/bind.hpp>
11 #include <boost/foreach.hpp>
12 #include <boost/tuple/tuple.hpp>
13 #include <boost/graph/graphviz.hpp>
14 #include <boost/graph/dominator_tree.hpp>
15 #include <boost/graph/reverse_graph.hpp>
16 #include <boost/graph/transpose_graph.hpp>
17 #include <boost/algorithm/string.hpp>
18 
19 namespace ssa_private
20 {
21 
23 template <class CFGNodeT, class CFGEdgeT>
24 class CFG : public boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
25  boost::shared_ptr<CFGNodeT>, boost::shared_ptr<CFGEdgeT> >
26 {
27 public:
28  typedef typename boost::graph_traits<CFG<CFGNodeT, CFGEdgeT> > GraphTraits;
29 
30 
31  typedef CFGNodeT CFGNodeType;
32  typedef CFGEdgeT CFGEdgeType;
33 
34  typedef boost::shared_ptr<CFGNodeType> CFGNodePtr;
35  typedef boost::shared_ptr<CFGEdgeType> CFGEdgePtr;
36 
37  typedef typename GraphTraits::vertex_descriptor Vertex;
38  typedef typename GraphTraits::edge_descriptor Edge;
39 
40  typedef std::map<Vertex, Vertex> VertexVertexMap;
41 
42 protected:
43 
46 
48  Vertex entry_;
49 
51  Vertex exit_;
52 
54  std::map<CFGNodeType, Vertex> nodesToVertices_;
55 
57  VertexVertexMap dominatorTree_;
58 
60  VertexVertexMap postdominatorTree_;
61 
62 public:
63 
65  CFG()
66  : funcDef_(NULL),
67  entry_(GraphTraits::null_vertex()),
68  exit_(GraphTraits::null_vertex())
69  {
70  }
71 
73  explicit CFG(SgFunctionDefinition* funcDef)
74  : funcDef_(funcDef),
75  entry_(GraphTraits::null_vertex()),
76  exit_(GraphTraits::null_vertex())
77  {
78  build(funcDef);
79  }
80 
82  void build(SgFunctionDefinition* funcDef);
83 
86  { return funcDef_; }
87 
89  const Vertex& getEntry() const
90  { return entry_; }
91 
93  const Vertex& getExit() const
94  { return exit_; }
95 
98  const VertexVertexMap& getDominatorTree();
99 
101  const VertexVertexMap& getPostdominatorTree();
102 
105 
107  std::vector<CFGNodePtr> getAllNodes() const;
108 
110  std::vector<CFGEdgePtr> getAllEdges() const;
111 
114  Vertex getVertexForNode(const CFGNodeType &node) const;
115 
117  std::vector<Edge> getAllBackEdges();
118 
120  std::vector<Vertex> getAllLoopHeaders();
121 
122 protected:
123 
125  void buildCFG(const CFGNodeType& node,
126  std::map<CFGNodeType, Vertex>& nodesAdded,
127  std::set<CFGNodeType>& nodesProcessed);
128 
130  void setEntryAndExit();
131 
134  {
136  : cfg1(g1), cfg2(g2) {}
137 
138  void operator()(const Vertex& v1, Vertex& v2) const
139  { cfg2[v2] = cfg1[v1]; }
140 
141  const CFG<CFGNodeT, CFGEdgeT>& cfg1;
143  };
144 
146  struct EdgeCopier
147  {
149  : cfg1(g1), cfg2(g2) {}
150 
151  void operator()(const Edge& e1, Edge& e2) const
152  { cfg2[e2] = cfg1[e1]; }
153 
154  const CFG<CFGNodeT, CFGEdgeT>& cfg1;
156  };
157 };
158 
159 
160 
161 
162 
163 template <class CFGNodeT, class CFGEdgeT>
165 {
166  ROSE_ASSERT(funcDef);
167  funcDef_ = funcDef;
168 
169  // The following two variables are used to record the nodes traversed.
170  nodesToVertices_.clear();
171  std::set<CFGNodeType> nodesProcessed;
172 
173  // Remove all nodes and edges first.
174  this->clear();
175  entry_ = GraphTraits::null_vertex();
176  exit_ = GraphTraits::null_vertex();
177 
178  buildCFG(CFGNodeType(funcDef->cfgForBeginning()), nodesToVertices_, nodesProcessed);
179 
180  // Find the entry and exit of this CFG.
181  setEntryAndExit();
182 
183  ROSE_ASSERT(isSgFunctionDefinition((*this)[entry_]->getNode()));
184  ROSE_ASSERT(isSgFunctionDefinition((*this)[exit_]->getNode()));
185 }
186 
187 template <class CFGNodeT, class CFGEdgeT>
189 {
190  BOOST_FOREACH (Vertex v, boost::vertices(*this))
191  {
192  CFGNodePtr node = (*this)[v];
193  if (isSgFunctionDefinition(node->getNode()))
194  {
195  if (node->getIndex() == 0)
196  entry_ = v;
197  else if (node->getIndex() == 3)
198  exit_ = v;
199  }
200  }
201 
202  //In graphs with an infinite loop, we might never get to the end vertex
203  //In those cases, we need to add it explicitly
204  if (exit_ == GraphTraits::null_vertex())
205  {
206  std::cerr << "This function may contain an infinite loop "
207  "inside so that its CFG cannot be built" << std::endl;
208  exit_ = add_vertex(*this);
209  (*this)[exit_] = CFGNodePtr(new CFGNodeType(funcDef_->cfgForEnd()));
210  }
211 
212  ROSE_ASSERT(entry_ != GraphTraits::null_vertex());
213  ROSE_ASSERT(exit_ != GraphTraits::null_vertex());
214 }
215 
216 template <class CFGNodeT, class CFGEdgeT>
218  const CFGNodeType& node,
219  std::map<CFGNodeType, Vertex>& nodesAdded,
220  std::set<CFGNodeType>& nodesProcessed)
221 {
222  ROSE_ASSERT(node.getNode());
223 
224  if (nodesProcessed.count(node) > 0)
225  return;
226  nodesProcessed.insert(node);
227 
228  typename std::map<CFGNodeType, Vertex>::iterator iter;
229  bool inserted;
230  Vertex from, to;
231 
232  // Add the source node.
233  const CFGNodeType& src = node;
234  ROSE_ASSERT(src.getNode());
235 
236  boost::tie(iter, inserted) = nodesAdded.insert(std::make_pair(src, Vertex()));
237 
238  if (inserted)
239  {
240  from = add_vertex(*this);
241  (*this)[from] = CFGNodePtr(new CFGNodeType(src));
242  iter->second = from;
243  }
244  else
245  {
246  from = iter->second;
247  }
248 
249  std::vector<CFGEdgeType> outEdges = node.outEdges();
250 
251  BOOST_FOREACH(const CFGEdgeType& cfgEdge, outEdges)
252  {
253  // For each out edge, add the target node.
254  CFGNodeType tar = cfgEdge.target();
255  ROSE_ASSERT(tar.getNode());
256 
257  boost::tie(iter, inserted) = nodesAdded.insert(std::make_pair(tar, Vertex()));
258 
259  if (inserted)
260  {
261  to = add_vertex(*this);
262  (*this)[to] = CFGNodePtr(new CFGNodeType(tar));
263  iter->second = to;
264  }
265  else
266  {
267  to = iter->second;
268  }
269 
270  // Add the edge.
271  Edge edge = add_edge(from, to, *this).first;
272  (*this)[edge] = CFGEdgePtr(new CFGEdgeType(cfgEdge));
273 
274  // Build the CFG recursively.
275  buildCFG(tar, nodesAdded, nodesProcessed);
276  }
277 }
278 
279 template <class CFGNodeT, class CFGEdgeT>
280 const typename CFG<CFGNodeT, CFGEdgeT>::VertexVertexMap& CFG<CFGNodeT, CFGEdgeT>::getDominatorTree()
281 {
282  if (!dominatorTree_.empty())
283  return dominatorTree_;
284 
285  boost::associative_property_map<VertexVertexMap> domTreePredMap(dominatorTree_);
286 
287  // Here we use the algorithm in boost::graph to build a map from each node to its immediate dominator.
288  boost::lengauer_tarjan_dominator_tree(*this, entry_, domTreePredMap);
289  return dominatorTree_;
290 }
291 
292 template <class CFGNodeT, class CFGEdgeT>
293 const typename CFG<CFGNodeT, CFGEdgeT>::VertexVertexMap& CFG<CFGNodeT, CFGEdgeT>::getPostdominatorTree()
294 {
295  if (!postdominatorTree_.empty())
296  return postdominatorTree_;
297 
298  boost::associative_property_map<VertexVertexMap> postdomTreePredMap(postdominatorTree_);
299 
300  // Here we use the algorithm in boost::graph to build an map from each node to its immediate dominator.
301  boost::lengauer_tarjan_dominator_tree(boost::make_reverse_graph(*this), exit_, postdomTreePredMap);
302  return postdominatorTree_;
303 }
304 
305 template <class CFGNodeT, class CFGEdgeT>
307 {
308  CFG<CFGNodeT, CFGEdgeT> reverseCFG;
309  // The following function makes a reverse CFG copy.
310  boost::transpose_graph(*this, reverseCFG,
311  boost::vertex_copy(VertexCopier(*this, reverseCFG)).
312  edge_copy(EdgeCopier(*this, reverseCFG)));
313 
314  // Swap entry and exit.
315  reverseCFG.entry_ = this->exit_;
316  reverseCFG.exit_ = this->entry_;
317  return reverseCFG;
318 }
319 
320 template <class CFGNodeT, class CFGEdgeT>
321 std::vector<typename CFG<CFGNodeT, CFGEdgeT>::CFGNodePtr>
323 {
324  std::vector<CFGNodePtr> allNodes;
325  BOOST_FOREACH (Vertex v, boost::vertices(*this))
326  allNodes.push_back((*this)[v]);
327  return allNodes;
328 }
329 
330 template <class CFGNodeT, class CFGEdgeT>
331 std::vector<typename CFG<CFGNodeT, CFGEdgeT>::CFGEdgePtr>
333 {
334  std::vector<CFGEdgePtr> allEdges;
335  BOOST_FOREACH (const Edge& e, boost::edges(*this))
336  allEdges.push_back((*this)[e]);
337  return allEdges;
338 }
339 
340 template <class CFGNodeT, class CFGEdgeT>
341 typename CFG<CFGNodeT, CFGEdgeT>::Vertex CFG<CFGNodeT, CFGEdgeT>::getVertexForNode(const CFGNodeType &node) const
342 {
343  typename std::map<CFGNodeType, Vertex>::const_iterator vertexIter = nodesToVertices_.find(node);
344  if (vertexIter == nodesToVertices_.end())
345  return GraphTraits::null_vertex();
346  else
347  {
348  ROSE_ASSERT(*(*this)[vertexIter->second] == node);
349  return vertexIter->second;
350  }
351 }
352 
353 template <class CFGNodeT, class CFGEdgeT>
354 std::vector<typename CFG<CFGNodeT, CFGEdgeT>::Edge> CFG<CFGNodeT, CFGEdgeT>::getAllBackEdges()
355 {
356  std::vector<Edge> backEdges;
357 
358  // If the dominator tree is not built yet, build it now.
359  getDominatorTree();
360 
361  BOOST_FOREACH (const Edge& e, boost::edges(*this))
362  {
363  Vertex src = boost::source(e, *this);
364  Vertex tar = boost::target(e, *this);
365 
366  //Vertex v = *(dominatorTree.find(src));
367  typename VertexVertexMap::const_iterator iter = dominatorTree_.find(src);
368  while (iter != dominatorTree_.end())
369  {
370  if (iter->second == tar)
371  {
372  backEdges.push_back(e);
373  break; // break the while loop
374  }
375  iter = dominatorTree_.find(iter->second);
376  }
377  }
378 
379  return backEdges;
380 }
381 
382 template <class CFGNodeT, class CFGEdgeT>
383 std::vector<typename CFG<CFGNodeT, CFGEdgeT>::Vertex> CFG<CFGNodeT, CFGEdgeT>::getAllLoopHeaders()
384 {
385  std::vector<Edge> backEdges = getAllBackEdges();
386  std::vector<Vertex> headers;
387  BOOST_FOREACH (Edge e, backEdges)
388  headers.push_back(boost::target(e, *this));
389  return headers;
390 }
391 
392 }
393 
394 
395 
CFG(SgFunctionDefinition *funcDef)
The constructor building the CFG.
Definition: boostGraphCFG.h:73
Vertex entry_
The entry node.
Definition: boostGraphCFG.h:48
Vertex exit_
The exit node.
Definition: boostGraphCFG.h:51
A class holding a Control Flow Graph.
Definition: boostGraphCFG.h:24
SgFunctionDefinition * getFunctionDefinition() const
Get the function definition of this CFG.
Definition: boostGraphCFG.h:85
VertexVertexMap dominatorTree_
The dominator tree of this CFG.
Definition: boostGraphCFG.h:57
std::vector< Vertex > getAllLoopHeaders()
Get all loop headers in this CFG. A natural loop only has one header.
This class represents the concept of a scope in C++ (e.g. global scope, fuction scope, etc.).
void buildCFG(const CFGNodeType &node, std::map< CFGNodeType, Vertex > &nodesAdded, std::set< CFGNodeType > &nodesProcessed)
A internal funtion which builds the actual CFG (boost::graph).
void build(SgFunctionDefinition *funcDef)
Build the actual CFG for the given function.
const VertexVertexMap & getPostdominatorTree()
Build the postdominator tree of this CFG.
const Vertex & getExit() const
Get the exit node of the CFG.
Definition: boostGraphCFG.h:93
CFG< CFGNodeT, CFGEdgeT > makeReverseCopy() const
Build a reverse CFG.
This class is used to copy edges when calling copy_graph().
std::vector< CFGNodePtr > getAllNodes() const
Get all CFG nodes in this graph.
Vertex getVertexForNode(const CFGNodeType &node) const
Given a CFG node, returns the corresponding vertex in the graph.
VirtualCFG::CFGNode cfgForBeginning()
Returns the CFG node for just before this AST node.
const Vertex & getEntry() const
Get the entry node of the CFG.
Definition: boostGraphCFG.h:89
SgFunctionDefinition * funcDef_
The function definition of this CFG.
Definition: boostGraphCFG.h:45
const VertexVertexMap & getDominatorTree()
Build the dominator tree of this CFG.
std::map< CFGNodeType, Vertex > nodesToVertices_
A map from a CFG node to the corresponding vertex.
Definition: boostGraphCFG.h:54
CFG()
The default constructor.
Definition: boostGraphCFG.h:65
void setEntryAndExit()
Find the entry and exit of this CFG and set the corresponding members.
VertexVertexMap postdominatorTree_
The postdominator tree of this CFG.
Definition: boostGraphCFG.h:60
std::vector< Edge > getAllBackEdges()
Get all back edges in the CFG. A back edge is one whose target dominates its source.
This class is used to copy vertices when calling copy_graph().
std::vector< CFGEdgePtr > getAllEdges() const
Get all CFG edges in this graph.