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>
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> >
28 typedef typename boost::graph_traits<CFG<CFGNodeT, CFGEdgeT> > GraphTraits;
31 typedef CFGNodeT CFGNodeType;
32 typedef CFGEdgeT CFGEdgeType;
34 typedef boost::shared_ptr<CFGNodeType> CFGNodePtr;
35 typedef boost::shared_ptr<CFGEdgeType> CFGEdgePtr;
37 typedef typename GraphTraits::vertex_descriptor
Vertex;
38 typedef typename GraphTraits::edge_descriptor
Edge;
40 typedef std::map<Vertex, Vertex> VertexVertexMap;
67 entry_(GraphTraits::null_vertex()),
68 exit_(GraphTraits::null_vertex())
75 entry_(GraphTraits::null_vertex()),
76 exit_(GraphTraits::null_vertex())
125 void buildCFG(
const CFGNodeType& node,
126 std::map<CFGNodeType, Vertex>& nodesAdded,
127 std::set<CFGNodeType>& nodesProcessed);
136 : cfg1(g1), cfg2(g2) {}
139 { cfg2[v2] = cfg1[v1]; }
149 : cfg1(g1), cfg2(g2) {}
151 void operator()(
const Edge& e1,
Edge& e2)
const
152 { cfg2[e2] = cfg1[e1]; }
163 template <
class CFGNodeT,
class CFGEdgeT>
166 ROSE_ASSERT(funcDef);
170 nodesToVertices_.clear();
171 std::set<CFGNodeType> nodesProcessed;
175 entry_ = GraphTraits::null_vertex();
176 exit_ = GraphTraits::null_vertex();
178 buildCFG(CFGNodeType(funcDef->
cfgForBeginning()), nodesToVertices_, nodesProcessed);
183 ROSE_ASSERT(isSgFunctionDefinition((*
this)[entry_]->getNode()));
184 ROSE_ASSERT(isSgFunctionDefinition((*
this)[exit_]->getNode()));
187 template <
class CFGNodeT,
class CFGEdgeT>
190 BOOST_FOREACH (
Vertex v, boost::vertices(*
this))
192 CFGNodePtr node = (*this)[v];
193 if (isSgFunctionDefinition(node->getNode()))
195 if (node->getIndex() == 0)
197 else if (node->getIndex() == 3)
204 if (exit_ == GraphTraits::null_vertex())
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()));
212 ROSE_ASSERT(entry_ != GraphTraits::null_vertex());
213 ROSE_ASSERT(exit_ != GraphTraits::null_vertex());
216 template <
class CFGNodeT,
class CFGEdgeT>
218 const CFGNodeType& node,
219 std::map<CFGNodeType, Vertex>& nodesAdded,
220 std::set<CFGNodeType>& nodesProcessed)
222 ROSE_ASSERT(node.getNode());
224 if (nodesProcessed.count(node) > 0)
226 nodesProcessed.insert(node);
228 typename std::map<CFGNodeType, Vertex>::iterator iter;
233 const CFGNodeType& src = node;
234 ROSE_ASSERT(src.getNode());
236 boost::tie(iter, inserted) = nodesAdded.insert(std::make_pair(src,
Vertex()));
240 from = add_vertex(*
this);
241 (*this)[from] = CFGNodePtr(
new CFGNodeType(src));
249 std::vector<CFGEdgeType> outEdges = node.outEdges();
251 BOOST_FOREACH(
const CFGEdgeType& cfgEdge, outEdges)
254 CFGNodeType tar = cfgEdge.target();
255 ROSE_ASSERT(tar.getNode());
257 boost::tie(iter, inserted) = nodesAdded.insert(std::make_pair(tar,
Vertex()));
261 to = add_vertex(*
this);
262 (*this)[to] = CFGNodePtr(
new CFGNodeType(tar));
271 Edge edge = add_edge(from, to, *
this).first;
272 (*this)[edge] = CFGEdgePtr(
new CFGEdgeType(cfgEdge));
275 buildCFG(tar, nodesAdded, nodesProcessed);
279 template <
class CFGNodeT,
class CFGEdgeT>
282 if (!dominatorTree_.empty())
283 return dominatorTree_;
285 boost::associative_property_map<VertexVertexMap> domTreePredMap(dominatorTree_);
288 boost::lengauer_tarjan_dominator_tree(*
this, entry_, domTreePredMap);
289 return dominatorTree_;
292 template <
class CFGNodeT,
class CFGEdgeT>
295 if (!postdominatorTree_.empty())
296 return postdominatorTree_;
298 boost::associative_property_map<VertexVertexMap> postdomTreePredMap(postdominatorTree_);
301 boost::lengauer_tarjan_dominator_tree(boost::make_reverse_graph(*
this), exit_, postdomTreePredMap);
302 return postdominatorTree_;
305 template <
class CFGNodeT,
class CFGEdgeT>
310 boost::transpose_graph(*
this, reverseCFG,
315 reverseCFG.
entry_ = this->exit_;
316 reverseCFG.
exit_ = this->entry_;
320 template <
class CFGNodeT,
class CFGEdgeT>
321 std::vector<typename CFG<CFGNodeT, CFGEdgeT>::CFGNodePtr>
324 std::vector<CFGNodePtr> allNodes;
325 BOOST_FOREACH (
Vertex v, boost::vertices(*
this))
326 allNodes.push_back((*
this)[v]);
330 template <
class CFGNodeT,
class CFGEdgeT>
331 std::vector<typename CFG<CFGNodeT, CFGEdgeT>::CFGEdgePtr>
334 std::vector<CFGEdgePtr> allEdges;
335 BOOST_FOREACH (
const Edge& e, boost::edges(*
this))
336 allEdges.push_back((*
this)[e]);
340 template <
class CFGNodeT,
class CFGEdgeT>
343 typename std::map<CFGNodeType, Vertex>::const_iterator vertexIter = nodesToVertices_.find(node);
344 if (vertexIter == nodesToVertices_.end())
345 return GraphTraits::null_vertex();
348 ROSE_ASSERT(*(*
this)[vertexIter->second] == node);
349 return vertexIter->second;
353 template <
class CFGNodeT,
class CFGEdgeT>
356 std::vector<Edge> backEdges;
361 BOOST_FOREACH (
const Edge& e, boost::edges(*
this))
363 Vertex src = boost::source(e, *
this);
364 Vertex tar = boost::target(e, *
this);
367 typename VertexVertexMap::const_iterator iter = dominatorTree_.find(src);
368 while (iter != dominatorTree_.end())
370 if (iter->second == tar)
372 backEdges.push_back(e);
375 iter = dominatorTree_.find(iter->second);
382 template <
class CFGNodeT,
class CFGEdgeT>
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));