ROSE  0.9.9.109
graphTemplate.h
1 #ifndef BACKSTROKE_CFG_H
2 #define BACKSTROKE_CFG_H
3 
4 
5 #include <rose.h>
6 #include <boost/graph/adjacency_list.hpp>
7 #include <boost/bind.hpp>
8 #include <boost/foreach.hpp>
9 #include <boost/tuple/tuple.hpp>
10 #include <boost/graph/graphviz.hpp>
11 #include <boost/graph/dominator_tree.hpp>
12 #include <boost/graph/reverse_graph.hpp>
13 #include <boost/graph/transpose_graph.hpp>
14 #include <boost/algorithm/string.hpp>
15 
16 
17 namespace Backstroke
18 {
19 
20 #define foreach BOOST_FOREACH
21 
22 
24 template <class CFGNodeType>
25 void writeCFGNode(std::ostream& out, const CFGNodeType& cfgNode)
26 {
27  SgNode* node = cfgNode.getNode();
28  ROSE_ASSERT(node);
29 
30  std::string nodeColor = "black";
31  if (isSgStatement(node))
32  nodeColor = "blue";
33  else if (isSgExpression(node))
34  nodeColor = "green";
35  else if (isSgInitializedName(node))
36  nodeColor = "red";
37 
38  std::string label;
39 
40  if (SgFunctionDefinition* funcDef = isSgFunctionDefinition(node))
41  {
42  std::string funcName = funcDef->get_declaration()->get_name().str();
43  if (cfgNode.getIndex() == 0)
44  label = "Entry\\n" + funcName;
45  else if (cfgNode.getIndex() == 3)
46  label = "Exit\\n" + funcName;
47  }
48 
49  if (!isSgScopeStatement(node) && !isSgCaseOptionStmt(node) && !isSgDefaultOptionStmt(node))
50  {
51  std::string content = node->unparseToString();
52  boost::replace_all(content, "\"", "\\\"");
53  boost::replace_all(content, "\\n", "\\\\n");
54  label += content;
55  }
56  else
57  label += "<" + node->class_name() + ">";
58 
59  if (label == "")
60  label += "<" + node->class_name() + ">";
61 
62  out << "[label=\"" << label << "\", color=\"" << nodeColor <<
63  "\", style=\"" << (cfgNode.isInteresting()? "solid" : "dotted") << "\"]";
64 }
65 
66 
68 template <class CFGEdgeType>
69 void writeCFGEdge(std::ostream& out, const CFGEdgeType& e)
70 {
71  out << "[label=\"" << escapeString(e.toString()) <<
72  "\", style=\"" << "solid" << "\"]";
73 }
74 
75 
76 // Predeclaration of class CFG.
77 template <class CFGNodeFilter> class CFG;
78 
80 {
81  bool operator()(const VirtualCFG::CFGNode& cfgNode) const
82  { return true; }
83 };
84 
86 {
87  bool operator()(const VirtualCFG::CFGNode& cfgNode) const
88  { return cfgNode.isInteresting(); }
89 };
90 
93 
94 
97 
98 
99 
100 
101 
102 /********************************************************************/
103 // The concept required to be fulfilled by CFGNodeFilter is
104 //
105 // struct CFGNodeFilter
106 // {
107 // bool operator()(const VirtualCFG::CFGNode& cfgNode) const;
108 // };
109 //
110 /********************************************************************/
111 
113 
114 template <class CFGNodeFilter>
115 class CFG : public boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
116  boost::shared_ptr<VirtualCFG::FilteredCFGNode<CFGNodeFilter> >,
117  boost::shared_ptr<VirtualCFG::FilteredCFGEdge<CFGNodeFilter> > >
118 {
119  typedef typename boost::graph_traits<CFG<CFGNodeFilter> > GraphTraits;
120 
121 public:
122  typedef VirtualCFG::FilteredCFGNode<CFGNodeFilter> CFGNodeType;
123  typedef VirtualCFG::FilteredCFGEdge<CFGNodeFilter> CFGEdgeType;
124 
125  typedef boost::shared_ptr<CFGNodeType> CFGNodePtr;
126  typedef boost::shared_ptr<CFGEdgeType> CFGEdgePtr;
127 
128  typedef typename GraphTraits::vertex_descriptor Vertex;
129  typedef typename GraphTraits::edge_descriptor Edge;
130 
131  typedef std::map<Vertex, Vertex> VertexVertexMap;
133  Vertex entry_;
134 
136  Vertex exit_;
137 
138 
139 protected:
140 
143 
144 
146  std::map<CFGNodeType, Vertex> nodesToVertices_;
147 
149  VertexVertexMap dominatorTree_;
150 
152  VertexVertexMap postdominatorTree_;
153 
154 public:
155  std::map<CFGNodeType, Vertex> getNodeVert() {
156  return nodesToVertices_;
157  }
158 
160  CFG()
161  : funcDef_(NULL),
162  entry_(GraphTraits::null_vertex()),
163  exit_(GraphTraits::null_vertex())
164  {
165  }
166 
168  explicit CFG(SgFunctionDefinition* funcDef)
169  : funcDef_(funcDef),
170  entry_(GraphTraits::null_vertex()),
171  exit_(GraphTraits::null_vertex())
172  {
173  build(funcDef);
174  }
175 
177  void build(SgFunctionDefinition* funcDef);
178 
181  { return funcDef_; }
182 
184  const Vertex& getEntry() const
185  { return entry_; }
186 
188  const Vertex& getExit() const
189  { return exit_; }
190 
193  const VertexVertexMap& getDominatorTree();
194 
196  const VertexVertexMap& getPostdominatorTree();
197 
200 
202  void toDot(const std::string& filename) const;
203 
205  std::vector<CFGNodePtr> getAllNodes() const;
206 
208  std::vector<CFGEdgePtr> getAllEdges() const;
209 
212  Vertex getVertexForNode(const CFGNodeType &node) const;
213 
216  bool isReducible() const { return true; }
217 
219  std::vector<Edge> getAllBackEdges();
220 
222  std::vector<Vertex> getAllLoopHeaders();
223 
224 protected:
225 
227  void buildCFG(const CFGNodeType& node,
228  std::map<CFGNodeType, Vertex>& nodesAdded,
229  std::set<CFGNodeType>& nodesProcessed);
230 
232  void setEntryAndExit();
233 
235  void writeGraphNode(std::ostream& out, const Vertex& node) const
236  {
237  writeCFGNode(out, *(*this)[node]);
238  //VirtualCFG::printNode(out, (*this)[node]);
239  }
240 
242  void writeGraphEdge(std::ostream& out, const Edge& edge) const
243  {
244  writeCFGEdge(out, *(*this)[edge]);
245  //VirtualCFG::printEdge(out, (*this)[edge], true);
246  }
247 
250  {
252  : cfg1(g1), cfg2(g2) {}
253 
254  void operator()(const Vertex& v1, Vertex& v2) const
255  { cfg2[v2] = cfg1[v1]; }
256 
257  const CFG<CFGNodeFilter>& cfg1;
258  CFG<CFGNodeFilter>& cfg2;
259  };
260 
262  struct EdgeCopier
263  {
265  : cfg1(g1), cfg2(g2) {}
266 
267  void operator()(const Edge& e1, Edge& e2) const
268  { cfg2[e2] = cfg1[e1]; }
269 
270  const CFG<CFGNodeFilter>& cfg1;
271  CFG<CFGNodeFilter>& cfg2;
272  };
273 };
274 
275 
276 
277 template <class CFGNodeFilter>
278 void CFG<CFGNodeFilter>::toDot(const std::string& filename) const
279 {
280  std::ofstream ofile(filename.c_str(), std::ios::out);
281  boost::write_graphviz(ofile, *this,
282  boost::bind(&CFG<CFGNodeFilter>::writeGraphNode, this, ::_1, ::_2),
283  boost::bind(&CFG<CFGNodeFilter>::writeGraphEdge, this, ::_1, ::_2));
284 }
285 
286 template <class CFGNodeFilter>
288 {
289  ROSE_ASSERT(funcDef);
290  funcDef_ = funcDef;
291 
292  // The following two variables are used to record the nodes traversed.
293  nodesToVertices_.clear();
294  std::set<CFGNodeType> nodesProcessed;
295 
296  // Remove all nodes and edges first.
297  this->clear();
298  entry_ = GraphTraits::null_vertex();
299  exit_ = GraphTraits::null_vertex();
300 
301  buildCFG(CFGNodeType(funcDef->cfgForBeginning()), nodesToVertices_, nodesProcessed);
302 
303  // Find the entry and exit of this CFG.
304  setEntryAndExit();
305 
306  ROSE_ASSERT(isSgFunctionDefinition((*this)[entry_]->getNode()));
307  ROSE_ASSERT(isSgFunctionDefinition((*this)[exit_]->getNode()));
308 }
309 
310 template <class CFGNodeFilter>
312 {
313  foreach (Vertex v, boost::vertices(*this))
314  {
315  CFGNodePtr node = (*this)[v];
316  if (isSgFunctionDefinition(node->getNode()))
317  {
318  if (node->getIndex() == 0)
319  entry_ = v;
320  else if (node->getIndex() == 3)
321  exit_ = v;
322  }
323  }
324 
325  //In graphs with an infinite loop, we might never get to the end vertex
326  //In those cases, we need to add it explicitly
327  if (exit_ == GraphTraits::null_vertex())
328  {
329  std::cerr << "This function may contain an infinite loop "
330  "inside so that its CFG cannot be built" << std::endl;
331  exit_ = add_vertex(*this);
332  (*this)[exit_] = CFGNodePtr(new CFGNodeType(funcDef_->cfgForEnd()));
333  }
334 
335  ROSE_ASSERT(entry_ != GraphTraits::null_vertex());
336  ROSE_ASSERT(exit_ != GraphTraits::null_vertex());
337 }
338 
339 template <class CFGNodeFilter>
341  const CFGNodeType& node,
342  std::map<CFGNodeType, Vertex>& nodesAdded,
343  std::set<CFGNodeType>& nodesProcessed)
344 {
345  ROSE_ASSERT(node.getNode());
346 
347  if (nodesProcessed.count(node) > 0)
348  return;
349  nodesProcessed.insert(node);
350 
351  typename std::map<CFGNodeType, Vertex>::iterator iter;
352  bool inserted;
353  Vertex from, to;
354 
355  // Add the source node.
356  const CFGNodeType& src = node;
357  ROSE_ASSERT(src.getNode());
358 
359  boost::tie(iter, inserted) = nodesAdded.insert(std::make_pair(src, Vertex()));
360 
361  if (inserted)
362  {
363  from = add_vertex(*this);
364  (*this)[from] = CFGNodePtr(new CFGNodeType(src));
365  iter->second = from;
366  }
367  else
368  {
369  from = iter->second;
370  }
371 
372  std::vector<CFGEdgeType> outEdges = node.outEdges();
373 
374  foreach(const CFGEdgeType& cfgEdge, outEdges)
375  {
376  // For each out edge, add the target node.
377  CFGNodeType tar = cfgEdge.target();
378  ROSE_ASSERT(tar.getNode());
379 
380  boost::tie(iter, inserted) = nodesAdded.insert(std::make_pair(tar, Vertex()));
381 
382  if (inserted)
383  {
384  to = add_vertex(*this);
385  (*this)[to] = CFGNodePtr(new CFGNodeType(tar));
386  iter->second = to;
387  }
388  else
389  {
390  to = iter->second;
391  }
392 
393  // Add the edge.
394  Edge edge = add_edge(from, to, *this).first;
395  (*this)[edge] = CFGEdgePtr(new CFGEdgeType(cfgEdge));
396 
397  // Build the CFG recursively.
398  buildCFG(tar, nodesAdded, nodesProcessed);
399  }
400 }
401 
402 template <class CFGNodeFilter>
403 const typename CFG<CFGNodeFilter>::VertexVertexMap& CFG<CFGNodeFilter>::getDominatorTree()
404 {
405  if (!dominatorTree_.empty())
406  return dominatorTree_;
407 
408  boost::associative_property_map<VertexVertexMap> domTreePredMap(dominatorTree_);
409 
410  // Here we use the algorithm in boost::graph to build a map from each node to its immediate dominator.
411  boost::lengauer_tarjan_dominator_tree(*this, entry_, domTreePredMap);
412  return dominatorTree_;
413 }
414 
415 template <class CFGNodeFilter>
416 const typename CFG<CFGNodeFilter>::VertexVertexMap& CFG<CFGNodeFilter>::getPostdominatorTree()
417 {
418  if (!postdominatorTree_.empty())
419  return postdominatorTree_;
420 
421  boost::associative_property_map<VertexVertexMap> postdomTreePredMap(postdominatorTree_);
422 
423  // Here we use the algorithm in boost::graph to build an map from each node to its immediate dominator.
424  boost::lengauer_tarjan_dominator_tree(boost::make_reverse_graph(*this), exit_, postdomTreePredMap);
425  return postdominatorTree_;
426 }
427 
428 template <class CFGNodeFilter>
430 {
431  CFG<CFGNodeFilter> reverseCFG;
432  // The following function makes a reverse CFG copy.
433  boost::transpose_graph(*this, reverseCFG,
434  boost::vertex_copy(VertexCopier(*this, reverseCFG)).
435  edge_copy(EdgeCopier(*this, reverseCFG)));
436 
437  // Swap entry and exit.
438  reverseCFG.entry_ = this->exit_;
439  reverseCFG.exit_ = this->entry_;
440  return reverseCFG;
441 }
442 
443 
444 template <class CFGNodeFilter>
445 std::vector<typename CFG<CFGNodeFilter>::CFGNodePtr>
447 {
448  std::vector<CFGNodePtr> allNodes;
449  foreach (Vertex v, boost::vertices(*this))
450  allNodes.push_back((*this)[v]);
451  return allNodes;
452 }
453 
454 /*
455 template <class CFGNodeFilter>
456 std::vector<typename CFG<CFGNodeFilter>::CFGNodeType>
457 CFG<CFGNodeFilter>::getAllNodesNoPtrs() const
458 {
459  std::vector<CFGNodeType> allNodes;
460  foreach (Vertex v, boost::vertices(*this))
461  allNodes.push_back(&((*this)[v]));
462  return allNodes;
463 }
464 */
465 
466 template <class CFGNodeFilter>
467 std::vector<typename CFG<CFGNodeFilter>::CFGEdgePtr>
469 {
470  std::vector<CFGEdgePtr> allEdges;
471  foreach (const Edge& e, boost::edges(*this))
472  allEdges.push_back((*this)[e]);
473  return allEdges;
474 }
475 
476 template <class CFGNodeFilter>
477 typename CFG<CFGNodeFilter>::Vertex CFG<CFGNodeFilter>::getVertexForNode(const CFGNodeType &node) const
478 {
479  typename std::map<CFGNodeType, Vertex>::const_iterator vertexIter = nodesToVertices_.find(node);
480  if (vertexIter == nodesToVertices_.end())
481  return GraphTraits::null_vertex();
482  else
483  {
484  ROSE_ASSERT(*(*this)[vertexIter->second] == node);
485  return vertexIter->second;
486  }
487 }
488 
489 template <class CFGNodeFilter>
490 std::vector<typename CFG<CFGNodeFilter>::Edge> CFG<CFGNodeFilter>::getAllBackEdges()
491 {
492  std::vector<Edge> backEdges;
493 
494  // If the dominator tree is not built yet, build it now.
495  getDominatorTree();
496 
497  foreach (const Edge& e, boost::edges(*this))
498  {
499  Vertex src = boost::source(e, *this);
500  Vertex tar = boost::target(e, *this);
501 
502  //Vertex v = *(dominatorTree.find(src));
503  typename VertexVertexMap::const_iterator iter = dominatorTree_.find(src);
504  while (iter != dominatorTree_.end())
505  {
506  if (iter->second == tar)
507  {
508  backEdges.push_back(e);
509  break; // break the while loop
510  }
511  iter = dominatorTree_.find(iter->second);
512  }
513  }
514 
515  return backEdges;
516 }
517 
518 template <class CFGNodeFilter>
519 std::vector<typename CFG<CFGNodeFilter>::Vertex> CFG<CFGNodeFilter>::getAllLoopHeaders()
520 {
521  std::vector<Edge> backEdges = getAllBackEdges();
522  std::vector<Vertex> headers;
523  foreach (Edge e, backEdges)
524  headers.push_back(boost::target(e, *this));
525  return headers;
526 }
527 
528 #undef foreach
529 
530 } // End of namespace Backstroke
531 
532 
533 #endif /* BACKSTROKE_CFG_H */
std::vector< Vertex > getAllLoopHeaders()
Get all loop headers in this CFG. A natural loop only has one header.
This class is used to copy vertices when calling copy_graph().
CFG()
The default constructor.
VertexVertexMap postdominatorTree_
The postdominator tree of this CFG.
std::vector< CFGEdgePtr > getAllEdges() const
Get all CFG edges in this graph.
void build(SgFunctionDefinition *funcDef)
Build the actual CFG for the given function.
std::vector< CFGNodePtr > getAllNodes() const
Get all CFG nodes in this graph.
void setEntryAndExit()
Find the entry and exit of this CFG and set the corresponding members.
This class is used to copy edges when calling copy_graph().
const Vertex & getEntry() const
Get the entry node of the CFG.
Vertex exit_
The exit node.
void toDot(const std::string &filename) const
Output the graph to a DOT file.
This class represents the concept of a scope in C++ (e.g. global scope, fuction scope, etc.).
void writeGraphEdge(std::ostream &out, const Edge &edge) const
This function helps to write the DOT file for edges.
const VertexVertexMap & getDominatorTree()
Build the dominator tree of this CFG.
bool isReducible() const
Return if this CFG is reducible (if all loops are natural loops, the CFG is reducible).
virtual std::string unparseToString(SgUnparse_Info *info) const
This function unparses the AST node (excluding comments and unnecessary white space) ...
void buildCFG(const CFGNodeType &node, std::map< CFGNodeType, Vertex > &nodesAdded, std::set< CFGNodeType > &nodesProcessed)
A internal funtion which builds the actual CFG (boost::graph).
SgFunctionDefinition * getFunctionDefinition() const
Get the function definition of this CFG.
const Vertex & getExit() const
Get the exit node of the CFG.
A node in the control flow graph.
Definition: virtualCFG.h:67
Vertex entry_
The entry node.
const VertexVertexMap & getPostdominatorTree()
Build the postdominator tree of this CFG.
This class represents the base class for all IR nodes within Sage III.
Definition: Cxx_Grammar.h:8322
VirtualCFG::CFGNode cfgForBeginning()
Returns the CFG node for just before this AST node.
bool isInteresting() const
Test whether this node satisfies a (fairly arbitrary) standard for "interestingness".
SgFunctionDefinition * funcDef_
The function definition of this CFG.
virtual std::string class_name() const
returns a string representing the class name
CFG(SgFunctionDefinition *funcDef)
The constructor building the CFG.
std::map< CFGNodeType, Vertex > nodesToVertices_
A map from a CFG node to the corresponding vertex.
void writeGraphNode(std::ostream &out, const Vertex &node) const
This function helps to write the DOT file for vertices.
A class holding a Control Flow Graph.
Definition: graphTemplate.h:77
VertexVertexMap dominatorTree_
The dominator tree of this CFG.
CFG< CFGNodeFilter > makeReverseCopy() const
Build a reverse CFG.
Vertex getVertexForNode(const CFGNodeType &node) const
Given a CFG node, returns the corresponding vertex in the graph.
std::vector< Edge > getAllBackEdges()
Get all back edges in the CFG. A back edge is one whose target dominates its source.