1 //===--Graph.cpp--- implements Graph class ---------------- ------*- C++ -*--=//
3 // This implements Graph for helping in trace generation
4 // This graph gets used by "ProfilePaths" class
6 //===----------------------------------------------------------------------===//
8 #include "llvm/Transforms/Instrumentation/Graph.h"
9 #include "llvm/BasicBlock.h"
19 const graphListElement *findNodeInList(const Graph::nodeList &NL,
21 for(Graph::nodeList::const_iterator NI = NL.begin(), NE=NL.end(); NI != NE;
23 if (*NI->element== *N)
28 graphListElement *findNodeInList(Graph::nodeList &NL, Node *N) {
29 for(Graph::nodeList::iterator NI = NL.begin(), NE=NL.end(); NI != NE; ++NI)
30 if (*NI->element== *N)
35 //graph constructor with root and exit specified
36 Graph::Graph(std::vector<Node*> n, std::vector<Edge> e,
40 for(vector<Node* >::iterator x=n.begin(), en=n.end(); x!=en; ++x)
41 //nodes[*x] = list<graphListElement>();
42 nodes[*x] = vector<graphListElement>();
44 for(vector<Edge >::iterator x=e.begin(), en=e.end(); x!=en; ++x){
47 //nodes[ee.getFirst()].push_front(graphListElement(ee.getSecond(),w, ee.getRandId()));
48 nodes[ee.getFirst()].push_back(graphListElement(ee.getSecond(),w, ee.getRandId()));
53 //check whether graph has an edge
54 //having an edge simply means that there is an edge in the graph
55 //which has same endpoints as the given edge
56 bool Graph::hasEdge(Edge ed) const{
60 nodeList nli=getNodeList(ed.getFirst());
61 Node *nd2=ed.getSecond();
63 return (findNodeInList(nli,nd2)!=NULL);
68 //check whether graph has an edge, with a given wt
69 //having an edge simply means that there is an edge in the graph
70 //which has same endpoints as the given edge
71 //This function checks, moreover, that the wt of edge matches too
72 bool Graph::hasEdgeAndWt(Edge ed) const{
76 Node *nd2=ed.getSecond();
77 nodeList nli=getNodeList(ed.getFirst());
79 for(nodeList::iterator NI=nli.begin(), NE=nli.end(); NI!=NE; ++NI)
80 if(*NI->element == *nd2 && ed.getWeight()==NI->weight)
87 void Graph::addNode(Node *nd){
88 vector<Node *> lt=getAllNodes();
90 for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE;++LI){
95 nodes[nd] =vector<graphListElement>(); //list<graphListElement>();
99 //this adds an edge ONLY when
100 //the edge to be added doesn not already exist
101 //we "equate" two edges here only with their
103 void Graph::addEdge(Edge ed, int w){
104 nodeList &ndList = nodes[ed.getFirst()];
105 Node *nd2=ed.getSecond();
107 if(findNodeInList(nodes[ed.getFirst()], nd2))
110 //ndList.push_front(graphListElement(nd2,w, ed.getRandId()));
111 ndList.push_back(graphListElement(nd2,w, ed.getRandId()));//chng
113 //sort(ndList.begin(), ndList.end(), NodeListSort());
116 //add an edge EVEN IF such an edge already exists
117 //this may make a multi-graph
118 //which does happen when we add dummy edges
119 //to the graph, for compensating for back-edges
120 void Graph::addEdgeForce(Edge ed){
121 //nodes[ed.getFirst()].push_front(graphListElement(ed.getSecond(),
122 //ed.getWeight(), ed.getRandId()));
123 nodes[ed.getFirst()].push_back
124 (graphListElement(ed.getSecond(), ed.getWeight(), ed.getRandId()));
126 //sort(nodes[ed.getFirst()].begin(), nodes[ed.getFirst()].end(), NodeListSort());
130 //Note that it removes just one edge,
131 //the first edge that is encountered
132 void Graph::removeEdge(Edge ed){
133 nodeList &ndList = nodes[ed.getFirst()];
134 Node &nd2 = *ed.getSecond();
136 for(nodeList::iterator NI=ndList.begin(), NE=ndList.end(); NI!=NE ;++NI) {
137 if(*NI->element == nd2) {
144 //remove an edge with a given wt
145 //Note that it removes just one edge,
146 //the first edge that is encountered
147 void Graph::removeEdgeWithWt(Edge ed){
148 nodeList &ndList = nodes[ed.getFirst()];
149 Node &nd2 = *ed.getSecond();
151 for(nodeList::iterator NI=ndList.begin(), NE=ndList.end(); NI!=NE ;++NI) {
152 if(*NI->element == nd2 && NI->weight==ed.getWeight()) {
159 //set the weight of an edge
160 void Graph::setWeight(Edge ed){
161 graphListElement *El = findNodeInList(nodes[ed.getFirst()], ed.getSecond());
163 El->weight=ed.getWeight();
168 //get the list of successor nodes
169 vector<Node *> Graph::getSuccNodes(Node *nd) const {
170 nodeMapTy::const_iterator nli = nodes.find(nd);
171 assert(nli != nodes.end() && "Node must be in nodes map");
172 const nodeList &nl = nli->second;
175 for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI)
176 lt.push_back(NI->element);
181 //get the number of outgoing edges
182 int Graph::getNumberOfOutgoingEdges(Node *nd) const {
183 nodeMapTy::const_iterator nli = nodes.find(nd);
184 assert(nli != nodes.end() && "Node must be in nodes map");
185 const nodeList &nl = nli->second;
188 for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI)
194 //get the list of predecessor nodes
195 vector<Node *> Graph::getPredNodes(Node *nd) const{
197 for(nodeMapTy::const_iterator EI=nodes.begin(), EE=nodes.end(); EI!=EE ;++EI){
198 Node *lnode=EI->first;
199 const nodeList &nl = getNodeList(lnode);
201 const graphListElement *N = findNodeInList(nl, nd);
202 if (N) lt.push_back(lnode);
207 //get the number of predecessor nodes
208 int Graph::getNumberOfIncomingEdges(Node *nd) const{
210 for(nodeMapTy::const_iterator EI=nodes.begin(), EE=nodes.end(); EI!=EE ;++EI){
211 Node *lnode=EI->first;
212 const nodeList &nl = getNodeList(lnode);
213 for(Graph::nodeList::const_iterator NI = nl.begin(), NE=nl.end(); NI != NE;
215 if (*NI->element== *nd)
221 //get the list of all the vertices in graph
222 vector<Node *> Graph::getAllNodes() const{
224 for(nodeMapTy::const_iterator x=nodes.begin(), en=nodes.end(); x != en; ++x)
225 lt.push_back(x->first);
230 //get the list of all the vertices in graph
231 vector<Node *> Graph::getAllNodes(){
233 for(nodeMapTy::const_iterator x=nodes.begin(), en=nodes.end(); x != en; ++x)
234 lt.push_back(x->first);
239 //class to compare two nodes in graph
240 //based on their wt: this is used in
241 //finding the maximal spanning tree
242 struct compare_nodes {
243 bool operator()(Node *n1, Node *n2){
244 return n1->getWeight() < n2->getWeight();
249 static void printNode(Node *nd){
250 cerr<<"Node:"<<nd->getElement()->getName()<<"\n";
253 //Get the Maximal spanning tree (also a graph)
255 Graph* Graph::getMaxSpanningTree(){
256 //assume connected graph
258 Graph *st=new Graph();//max spanning tree, undirected edges
259 int inf=9999999;//largest key
260 vector<Node *> lt = getAllNodes();
262 //initially put all vertices in vector vt
264 //wt(others)=infinity
267 //pull out u: a vertex frm vt of min wt
268 //for all vertices w in vt,
269 //if wt(w) greater than
270 //the wt(u->w), then assign
271 //wt(w) to be wt(u->w).
273 //make parent(u)=w in the spanning tree
274 //keep pulling out vertices from vt till it is empty
278 map<Node*, Node* > parent;
279 map<Node*, int > ed_weight;
281 //initialize: wt(root)=0, wt(others)=infinity
282 //parent(root)=NULL, parent(others) not defined (but not null)
283 for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
285 if(*thisNode == *getRoot()){
286 thisNode->setWeight(0);
287 parent[thisNode]=NULL;
288 ed_weight[thisNode]=0;
291 thisNode->setWeight(inf);
293 st->addNode(thisNode);//add all nodes to spanning tree
294 //we later need to assign edges in the tree
295 vt.push_back(thisNode); //pushed all nodes in vt
298 //keep pulling out vertex of min wt from vt
300 Node *u=*(min_element(vt.begin(), vt.end(), compare_nodes()));
301 DEBUG(cerr<<"popped wt"<<(u)->getWeight()<<"\n";
304 if(parent[u]!=NULL){ //so not root
305 Edge edge(parent[u],u, ed_weight[u]); //assign edge in spanning tree
306 st->addEdge(edge,ed_weight[u]);
308 DEBUG(cerr<<"added:\n";
315 for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){
322 //assign wt(v) to all adjacent vertices v of u
324 Graph::nodeList nl=getNodeList(u);
325 for(nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){
327 int weight=-NI->weight;
328 //check if v is in vt
330 for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){
336 DEBUG(cerr<<"wt:v->wt"<<weight<<":"<<v->getWeight()<<"\n";
337 printNode(v);cerr<<"node wt:"<<(*v).weight<<"\n");
339 //so if v in in vt, change wt(v) to wt(u->v)
340 //only if wt(u->v)<wt(v)
341 if(contains && weight<v->getWeight()){
344 v->setWeight(weight);
346 DEBUG(cerr<<v->getWeight()<<":Set weight------\n";
348 printEdge(Edge(u,v,weight)));
355 //print the graph (for debugging)
356 void Graph::printGraph(){
357 vector<Node *> lt=getAllNodes();
358 cerr<<"Graph---------------------\n";
359 for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
360 cerr<<((*LI)->getElement())->getName()<<"->";
361 Graph::nodeList nl=getNodeList(*LI);
362 for(Graph::nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){
363 cerr<<":"<<"("<<(NI->element->getElement())
364 ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")";
371 //get a list of nodes in the graph
372 //in r-topological sorted order
373 //note that we assumed graph to be connected
374 vector<Node *> Graph::reverseTopologicalSort() const{
375 vector <Node *> toReturn;
376 vector<Node *> lt=getAllNodes();
377 for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
378 if((*LI)->getWeight()!=GREY && (*LI)->getWeight()!=BLACK)
379 DFS_Visit(*LI, toReturn);
384 //a private method for doing DFS traversal of graph
385 //this is used in determining the reverse topological sort
387 void Graph::DFS_Visit(Node *nd, vector<Node *> &toReturn) const {
389 vector<Node *> lt=getSuccNodes(nd);
390 for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
391 if((*LI)->getWeight()!=GREY && (*LI)->getWeight()!=BLACK)
392 DFS_Visit(*LI, toReturn);
394 toReturn.push_back(nd);
397 //Ordinarily, the graph is directional
398 //this converts the graph into an
399 //undirectional graph
400 //This is done by adding an edge
401 //v->u for all existing edges u->v
402 void Graph::makeUnDirectional(){
403 vector<Node* > allNodes=getAllNodes();
404 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
406 nodeList nl=getNodeList(*NI);
407 for(nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE; ++NLI){
408 Edge ed(NLI->element, *NI, NLI->weight);
409 if(!hasEdgeAndWt(ed)){
410 DEBUG(cerr<<"######doesn't hv\n";
418 //reverse the sign of weights on edges
419 //this way, max-spanning tree could be obtained
420 //usin min-spanning tree, and vice versa
421 void Graph::reverseWts(){
422 vector<Node *> allNodes=getAllNodes();
423 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
425 nodeList node_list=getNodeList(*NI);
426 for(nodeList::iterator NLI=nodes[*NI].begin(), NLE=nodes[*NI].end();
428 NLI->weight=-NLI->weight;
433 //getting the backedges in a graph
434 //Its a variation of DFS to get the backedges in the graph
435 //We get back edges by associating a time
436 //and a color with each vertex.
437 //The time of a vertex is the time when it was first visited
438 //The color of a vertex is initially WHITE,
439 //Changes to GREY when it is first visited,
440 //and changes to BLACK when ALL its neighbors
442 //So we have a back edge when we meet a successor of
443 //a node with smaller time, and GREY color
444 void Graph::getBackEdges(vector<Edge > &be) const{
445 map<Node *, Color > color;
447 vector<Node *> allNodes=getAllNodes();
449 for(vector<Node *>::const_iterator NI=allNodes.begin(), NE=allNodes.end();
451 if(color[*NI]!=GREY && color[*NI]!=BLACK)
452 getBackEdgesVisit(*NI, be, color, d, time);
456 //helper function to get back edges: it is called by
457 //the "getBackEdges" function above
458 void Graph::getBackEdgesVisit(Node *u, vector<Edge > &be,
459 map<Node *, Color > &color,
460 map<Node *, int > &d, int &time) const{
465 vector<graphListElement> succ_list=getNodeList(u);
466 for(vector<graphListElement>::const_iterator vl=succ_list.begin(),
467 ve=succ_list.end(); vl!=ve; ++vl){
469 // for(vector<Node *>::const_iterator v=succ_list.begin(), ve=succ_list.end();
472 if(color[v]!=GREY && color[v]!=BLACK){
473 getBackEdgesVisit(v, be, color, d, time);
476 //now checking for d and f vals
478 //so v is ancestor of u if time of u > time of v
480 Edge *ed=new Edge(u, v,vl->weight, vl->randId);
481 if (!(*u == *getExit() && *v == *getRoot()))
482 be.push_back(*ed); // choose the forward edges
486 color[u]=BLACK;//done with visiting the node and its neighbors