ROSE  0.9.9.109
SgGraphTemplate.h
1 #include <boost/graph/adjacency_list.hpp>
2 #include <boost/graph/astar_search.hpp>
3 //#include <graphProcessing.h>
4 #include <staticCFG.h>
5 #include <interproceduralCFG.h>
6 #include <rose.h>
7 struct Vertex{
9  CFGNode cfgnd;
10 };
11 
12 struct Edge {
13  SgDirectedGraphEdge* gedge;
14 };
15 
16 typedef boost::adjacency_list<
17  boost::vecS,
18  boost::vecS,
19  boost::bidirectionalS,
20  Vertex,
21  Edge
22 > myGraph;
23 
24 typedef myGraph::vertex_descriptor VertexID;
25 typedef myGraph::edge_descriptor EdgeID;
26 
27 //myGraph* instantiateGraph(SgIncidencedDirectedGraph* g, StaticCFG::CFG cfg);
28 std::pair<std::vector<SgGraphNode*>, std::vector<SgDirectedGraphEdge*> > getAllNodesAndEdges(SgIncidenceDirectedGraph* g, SgGraphNode* start);
29 std::map<VertexID, SgGraphNode*> getGraphNode;
30 std::map<SgGraphNode*, VertexID> VSlink;
31 
32 myGraph* instantiateGraph(SgIncidenceDirectedGraph*& g, StaticCFG::InterproceduralCFG& cfg, SgNode* pstart) {
33  //SgNode* prestart = cfg.getEntry();
34  //cfg.buildFullCFG();
35  CFGNode startN = cfg.getEntry();
36  SgGraphNode* start = cfg.toGraphNode(startN);
37  ROSE_ASSERT(startN != NULL);
38  ROSE_ASSERT(start != NULL);
39  myGraph* graph = new myGraph;
40  //std::map<SgGraphNode*, VertexID> VSlink;
41  std::pair<std::vector<SgGraphNode*>, std::vector<SgDirectedGraphEdge*> > alledsnds = getAllNodesAndEdges(g, start);
42  std::vector<SgGraphNode*> nods = alledsnds.first;
43  std::vector<SgDirectedGraphEdge*> eds = alledsnds.second;
44  std::set<std::pair<VertexID, VertexID> > prs;
45  //for (std::vector<vertex_descriptor> i = nods.begin(); i != nods.end(); i++) {
46  // VertexID vID = boost::add_vertex(graph);
47  // graph[vID].cfgnd = cfg->toCFGNode(*i);
48  //}
49  for (std::vector<SgDirectedGraphEdge*>::iterator j = eds.begin(); j != eds.end(); j++) {
50  SgDirectedGraphEdge* u = *j;
51  SgGraphNode* u1 = u->get_from();
52  SgGraphNode* u2 = u->get_to();
53  VertexID v1;
54  VertexID v2;
55  if (VSlink.find(u1) == VSlink.end()) {
56  v1 = boost::add_vertex(*graph);
57  getGraphNode[v1] = u1;
58  VSlink[u1] = v1;
59  (*graph)[v1].sg = u1;
60  (*graph)[v1].cfgnd = cfg.toCFGNode(u1);
61  }
62  else {
63  v1 = VSlink[u1];
64  }
65  if (VSlink.find(u2) != VSlink.end()) {
66  v2 = VSlink[u2];
67  }
68  else {
69  v2 = boost::add_vertex(*graph);
70  VSlink[u2] = v2;
71  (*graph)[v2].sg = u2;
72  getGraphNode[v2] = u2;
73  (*graph)[v2].cfgnd = cfg.toCFGNode(u2);
74  }
75  bool ok;
76  EdgeID uE;
77  std::pair<VertexID, VertexID> pr;
78  pr.first = v1;
79  pr.second = v2;
80  if (prs.find(pr) == prs.end()) {
81  prs.insert(pr);
82  boost::tie(uE, ok) = boost::add_edge(v1, v2, *graph);
83  }
84  }
85  //std::cout << "prs.size: " << prs.size() << std::endl;
86  return graph;
87 }
88 
89 
90 
91 myGraph* instantiateGraph(SgIncidenceDirectedGraph*& g, StaticCFG::CFG& cfg) {
92  SgGraphNode* start = cfg.getEntry();
93  myGraph* graph = new myGraph;
94  //std::map<SgGraphNode*, VertexID> VSlink;
95  std::pair<std::vector<SgGraphNode*>, std::vector<SgDirectedGraphEdge*> > alledsnds = getAllNodesAndEdges(g, start);
96  std::vector<SgGraphNode*> nods = alledsnds.first;
97  std::vector<SgDirectedGraphEdge*> eds = alledsnds.second;
98  std::set<std::pair<VertexID, VertexID> > prs;
99  //for (std::vector<vertex_descriptor> i = nods.begin(); i != nods.end(); i++) {
100  // VertexID vID = boost::add_vertex(graph);
101  // graph[vID].cfgnd = cfg->toCFGNode(*i);
102  //}
103  for (std::vector<SgDirectedGraphEdge*>::iterator j = eds.begin(); j != eds.end(); j++) {
104  SgDirectedGraphEdge* u = *j;
105  SgGraphNode* u1 = u->get_from();
106  SgGraphNode* u2 = u->get_to();
107  VertexID v1;
108  VertexID v2;
109  if (VSlink.find(u1) == VSlink.end()) {
110  v1 = boost::add_vertex(*graph);
111  getGraphNode[v1] = u1;
112  VSlink[u1] = v1;
113  (*graph)[v1].sg = u1;
114  (*graph)[v1].cfgnd = cfg.toCFGNode(u1);
115  }
116  else {
117  v1 = VSlink[u1];
118  }
119  if (VSlink.find(u2) != VSlink.end()) {
120  v2 = VSlink[u2];
121  }
122  else {
123  v2 = boost::add_vertex(*graph);
124  VSlink[u2] = v2;
125  (*graph)[v2].sg = u2;
126  getGraphNode[v2] = u2;
127  (*graph)[v2].cfgnd = cfg.toCFGNode(u2);
128  }
129  bool ok;
130  EdgeID uE;
131  std::pair<VertexID, VertexID> pr;
132  pr.first = v1;
133  pr.second = v2;
134  if (prs.find(pr) == prs.end()) {
135  prs.insert(pr);
136  boost::tie(uE, ok) = boost::add_edge(v1, v2, *graph);
137  }
138  }
139  //std::cout << "prs.size: " << prs.size() << std::endl;
140  return graph;
141 }
142 
143 
144 
145 
146 std::pair<std::vector<SgGraphNode*>, std::vector<SgDirectedGraphEdge*> > getAllNodesAndEdges(SgIncidenceDirectedGraph* g, SgGraphNode* start) {
147  //for (int i = 0; i < starts.size(); i++) {
148  SgGraphNode* n = start;
149  std::vector<SgGraphNode*> nods;
150  std::vector<SgGraphNode*> newnods;
151  std::set<SgDirectedGraphEdge*> edsnew;
152  std::vector<SgDirectedGraphEdge*> eds;
153  std::vector<SgDirectedGraphEdge*> feds;
154  std::vector<SgGraphNode*> fnods;
155  std::set<std::pair<EdgeID, EdgeID> > prs;
156  std::set<SgDirectedGraphEdge*> oeds = g->computeEdgeSetOut(start);
157  fnods.push_back(start);
158  newnods.push_back(n);
159 
160  while (oeds.size() > 0) {
161  for (std::set<SgDirectedGraphEdge*>::iterator j = oeds.begin(); j != oeds.end(); j++) {
162  //if (find(eds.begin(), eds.end(), *j) == eds.end()) {
163  if (find(feds.begin(), feds.end(), *j) == feds.end()) {
164  feds.push_back(*j);
165  edsnew.insert(*j);
166  }
167  if (find(fnods.begin(), fnods.end(), (*j)->get_to()) == fnods.end()) {
168  fnods.push_back((*j)->get_to());
169  }
170  newnods.push_back((*j)->get_to());
171  //}
172  }
173 
174  for (unsigned int i = 0; i < newnods.size(); i++) {
175  std::set<SgDirectedGraphEdge*> oedsp = g->computeEdgeSetOut(newnods[i]);
176  for (std::set<SgDirectedGraphEdge*>::iterator j = oedsp.begin(); j != oedsp.end(); j++) {
177  if (find(feds.begin(), feds.end(), *j) == feds.end()) {
178  // feds.push_back(*j);
179  edsnew.insert(*j);
180 
181  }
182  //if (find(fnods.begin(), fnods.end(), (*j)->get_to()) == fnods.end()) {
183  // fnods.push_back((*j)->get_to());
184  // newnods.push_back((*j)->get_to());
185  // }
186  // newnods.push_back((*j)->get_to());
187  }
188  }
189  nods = newnods;
190  oeds = edsnew;
191  edsnew.clear();
192  newnods.clear();
193  }
194  std::pair<std::vector<SgGraphNode*>, std::vector<SgDirectedGraphEdge*> > retpr;
195  retpr.first = fnods;
196  retpr.second = feds;
197  //std::cout << "fnods.size()" << fnods.size() << std::endl;
198  //std::cout << "feds.size()" << feds.size() << std::endl;
199  return retpr;
200 }
201 
SgGraphNode * getEntry() const
Get the entry node of the CFG.
Definition: staticCFG.h:73
SgGraphNode * toGraphNode(CFGNode &n)
Turn a CFG node into a GraphNode which is defined in VirtualCFG namespace.
Definition: staticCFG.h:53
This class represents the base class for all IR nodes within Sage III.
Definition: Cxx_Grammar.h:8322
CFGNode toCFGNode(SgGraphNode *node)
Turn a graph node into a CFGNode which is defined in VirtualCFG namespace.