ROSE 0.11.145.147
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>
7struct Vertex{
9 CFGNode cfgnd;
10};
11
12struct Edge {
14};
15
16typedef boost::adjacency_list<
17 boost::vecS,
18 boost::vecS,
19 boost::bidirectionalS,
20 Vertex,
21 Edge
22> myGraph;
23
24typedef myGraph::vertex_descriptor VertexID;
25typedef myGraph::edge_descriptor EdgeID;
26
27//myGraph* instantiateGraph(SgIncidencedDirectedGraph* g, StaticCFG::CFG cfg);
28std::pair<std::vector<SgGraphNode*>, std::vector<SgDirectedGraphEdge*> > getAllNodesAndEdges(SgIncidenceDirectedGraph* g, SgGraphNode* start);
29std::map<VertexID, SgGraphNode*> getGraphNode;
30std::map<SgGraphNode*, VertexID> VSlink;
31
32myGraph* 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
91myGraph* 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
146std::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
This class represents the base class for all IR nodes within Sage III.
SgGraphNode * getEntry() const
Get the entry node of the CFG.
Definition staticCFG.h:77
SgGraphNode * toGraphNode(CFGNode &n)
Turn a CFG node into a GraphNode which is defined in VirtualCFG namespace.
Definition staticCFG.h:53
CFGNode toCFGNode(SgGraphNode *node)
Turn a graph node into a CFGNode which is defined in VirtualCFG namespace.
This namespace contains template functions that operate on the ROSE AST.
Definition sageGeneric.h:38