lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp

   1 //===--Graph.cpp--- implements Graph class ---------------- ------*- C++ -*--=//
   2 //
   3 // This implements Graph for helping in trace generation
   4 // This graph gets used by "ProfilePaths" class
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #include "Graph.h"
   9 #include "llvm/BasicBlock.h"
  10 #include <algorithm>
  11 #include <iostream>
  12
  13 using std::list;
  14 using std::set;
  15 using std::map;
  16 using std::vector;
  17 using std::cerr;
  18
  19 static const graphListElement *findNodeInList(const Graph::nodeList &NL,
  20                                               Node *N) {
  21   for(Graph::nodeList::const_iterator NI = NL.begin(), NE=NL.end(); NI != NE;
  22       ++NI)
  23     if (*NI->element== *N)
  24       return &*NI;
  25   return 0;
  26 }
  27
  28 static 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)
  31       return &*NI;
  32   return 0;
  33 }
  34
  35 //graph constructor with root and exit specified
  36 Graph::Graph(std::set<Node*> n, std::set<Edge> e,
  37              Node *rt, Node *lt){
  38   strt=rt;
  39   ext=lt;
  40   for(set<Node* >::iterator x=n.begin(), en=n.end(); x!=en; ++x)
  41     nodes[*x] = list<graphListElement>();
  42
  43   for(set<Edge >::iterator x=e.begin(), en=e.end(); x!=en; ++x){
  44     Edge ee=*x;
  45     int w=ee.getWeight();
  46     nodes[ee.getFirst()].push_front(graphListElement(ee.getSecond(),w));
  47   }
  48
  49 }
  50
  51 //check whether graph has an edge
  52 //having an edge simply means that there is an edge in the graph
  53 //which has same endpoints as the given edge
  54 bool Graph::hasEdge(Edge ed) const{
  55   if(ed.isNull())
  56     return false;
  57
  58   nodeList nli=getNodeList(ed.getFirst());
  59   Node *nd2=ed.getSecond();
  60
  61   return (findNodeInList(nli,nd2)!=NULL);
  62
  63 }
  64
  65
  66 //check whether graph has an edge, with a given wt
  67 //having an edge simply means that there is an edge in the graph
  68 //which has same endpoints as the given edge
  69 //This function checks, moreover, that the wt of edge matches too
  70 bool Graph::hasEdgeAndWt(Edge ed) const{
  71   if(ed.isNull())
  72     return false;
  73
  74   Node *nd2=ed.getSecond();
  75   nodeList nli=getNodeList(ed.getFirst());
  76
  77   for(nodeList::iterator NI=nli.begin(), NE=nli.end(); NI!=NE; ++NI)
  78     if(*NI->element == *nd2 && ed.getWeight()==NI->weight)
  79       return true;
  80
  81   return false;
  82 }
  83
  84 //add a node
  85 void Graph::addNode(Node *nd){
  86   list<Node *> lt=getAllNodes();
  87
  88   for(list<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE;++LI){
  89     if(**LI==*nd)
  90       return;
  91   }
  92
  93   nodes[nd] = list<graphListElement>();
  94 }
  95
  96 //add an edge
  97 //this adds an edge ONLY when
  98 //the edge to be added doesn not already exist
  99 //we "equate" two edges here only with their
 100 //end points
 101 void Graph::addEdge(Edge ed, int w){
 102   nodeList &ndList = nodes[ed.getFirst()];
 103   Node *nd2=ed.getSecond();
 104
 105   if(findNodeInList(nodes[ed.getFirst()], nd2))
 106     return;
 107
 108   ndList.push_front(graphListElement(nd2,w));
 109 }
 110
 111 //add an edge EVEN IF such an edge already exists
 112 //this may make a multi-graph
 113 //which does happen when we add dummy edges
 114 //to the graph, for compensating for back-edges
 115 void Graph::addEdgeForce(Edge ed){
 116   nodes[ed.getFirst()].push_front(graphListElement(ed.getSecond(),
 117                                                    ed.getWeight()));
 118 }
 119
 120 //remove an edge
 121 //Note that it removes just one edge,
 122 //the first edge that is encountered
 123 void Graph::removeEdge(Edge ed){
 124   nodeList &ndList = nodes[ed.getFirst()];
 125   Node &nd2 = *ed.getSecond();
 126
 127   for(nodeList::iterator NI=ndList.begin(), NE=ndList.end(); NI!=NE ;++NI) {
 128     if(*NI->element == nd2) {
 129       ndList.erase(NI);
 130       break;
 131     }
 132   }
 133 }
 134
 135 //set the weight of an edge
 136 void Graph::setWeight(Edge ed){
 137   graphListElement *El = findNodeInList(nodes[ed.getFirst()], ed.getSecond());
 138   if (El)
 139     El->weight=ed.getWeight();
 140 }
 141
 142
 143
 144 //get the list of successor nodes
 145 list<Node *> Graph::getSuccNodes(Node *nd) const {
 146   nodeMapTy::const_iterator nli = nodes.find(nd);
 147   assert(nli != nodes.end() && "Node must be in nodes map");
 148   const nodeList &nl = nli->second;
 149
 150   list<Node *> lt;
 151   for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI)
 152     lt.push_back(NI->element);
 153
 154   return lt;
 155 }
 156
 157 //get the list of predecessor nodes
 158 list<Node *> Graph::getPredNodes(Node *nd) const{
 159   list<Node *> lt;
 160   for(nodeMapTy::const_iterator EI=nodes.begin(), EE=nodes.end(); EI!=EE ;++EI){
 161     Node *lnode=EI->first;
 162     const nodeList &nl = getNodeList(lnode);
 163
 164     const graphListElement *N = findNodeInList(nl, nd);
 165     if (N) lt.push_back(lnode);
 166   }
 167   return lt;
 168 }
 169
 170 //get the list of all the vertices in graph
 171 list<Node *> Graph::getAllNodes() const{
 172   list<Node *> lt;
 173   for(nodeMapTy::const_iterator x=nodes.begin(), en=nodes.end(); x != en; ++x)
 174     lt.push_back(x->first);
 175
 176   return lt;
 177 }
 178
 179
 180 //class to compare two nodes in graph
 181 //based on their wt: this is used in
 182 //finding the maximal spanning tree
 183 struct compare_nodes {
 184   bool operator()(Node *n1, Node *n2){
 185     return n1->getWeight() < n2->getWeight();
 186   }
 187 };
 188
 189
 190 static void printNode(Node *nd){
 191   cerr<<"Node:"<<nd->getElement()->getName()<<"\n";
 192 }
 193
 194 //Get the Maximal spanning tree (also a graph)
 195 //of the graph
 196 Graph* Graph::getMaxSpanningTree(){
 197   //assume connected graph
 198
 199   Graph *st=new Graph();//max spanning tree, undirected edges
 200   int inf=9999999;//largest key
 201   list<Node *> lt = getAllNodes();
 202
 203   //initially put all vertices in vector vt
 204   //assign wt(root)=0
 205   //wt(others)=infinity
 206   //
 207   //now:
 208   //pull out u: a vertex frm vt of min wt
 209   //for all vertices w in vt,
 210   //if wt(w) greater than
 211   //the wt(u->w), then assign
 212   //wt(w) to be wt(u->w).
 213   //
 214   //make parent(u)=w in the spanning tree
 215   //keep pulling out vertices from vt till it is empty
 216
 217   vector<Node *> vt;
 218
 219   map<Node*, Node* > parent;
 220   map<Node*, int > ed_weight;
 221
 222   //initialize: wt(root)=0, wt(others)=infinity
 223   //parent(root)=NULL, parent(others) not defined (but not null)
 224   for(list<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
 225     Node *thisNode=*LI;
 226     if(*thisNode == *getRoot()){
 227       thisNode->setWeight(0);
 228       parent[thisNode]=NULL;
 229       ed_weight[thisNode]=0;
 230     }
 231     else{
 232       thisNode->setWeight(inf);
 233     }
 234     st->addNode(thisNode);//add all nodes to spanning tree
 235     //we later need to assign edges in the tree
 236     vt.push_back(thisNode); //pushed all nodes in vt
 237   }
 238
 239   //keep pulling out vertex of min wt from vt
 240   while(!vt.empty()){
 241     Node *u=*(min_element(vt.begin(), vt.end(), compare_nodes()));
 242 #ifdef DEBUG_PATH_PROFILES
 243     cerr<<"popped wt"<<(u)->getWeight()<<"\n";
 244     printNode(u);
 245 #endif
 246     if(parent[u]!=NULL){ //so not root
 247       Edge edge(parent[u],u, ed_weight[u]); //assign edge in spanning tree
 248       st->addEdge(edge,ed_weight[u]);
 249 #ifdef DEBUG_PATH_PROFILES
 250       cerr<<"added:\n";
 251       printEdge(edge);
 252 #endif
 253     }
 254
 255     //vt.erase(u);
 256
 257     //remove u frm vt
 258     for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){
 259       if(**VI==*u){
 260         vt.erase(VI);
 261         break;
 262       }
 263     }
 264
 265     //assign wt(v) to all adjacent vertices v of u
 266     //only if v is in vt
 267     Graph::nodeList nl=getNodeList(u);
 268     for(nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){
 269       Node *v=NI->element;
 270       int weight=-NI->weight;
 271       //check if v is in vt
 272       bool contains=false;
 273       for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){
 274         if(**VI==*v){
 275           contains=true;
 276           break;
 277         }
 278       }
 279 #ifdef DEBUG_PATH_PROFILES
 280       cerr<<"wt:v->wt"<<weight<<":"<<v->getWeight()<<"\n";
 281       printNode(v);cerr<<"node wt:"<<(*v).weight<<"\n";
 282 #endif
 283       //so if v in in vt, change wt(v) to wt(u->v)
 284       //only if wt(u->v)<wt(v)
 285       if(contains && weight<v->getWeight()){
 286         parent[v]=u;
 287         ed_weight[v]=weight;
 288         v->setWeight(weight);
 289 #ifdef DEBUG_PATH_PROFILES
 290         cerr<<v->getWeight()<<":Set weight------\n";
 291         printGraph();
 292         printEdge(Edge(u,v,weight));
 293 #endif
 294       }
 295     }
 296   }
 297   return st;
 298 }
 299
 300 //print the graph (for debugging)
 301 void Graph::printGraph(){
 302    list<Node *> lt=getAllNodes();
 303    cerr<<"Graph---------------------\n";
 304    for(list<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
 305      cerr<<((*LI)->getElement())->getName()<<"->";
 306      Graph::nodeList nl=getNodeList(*LI);
 307      for(Graph::nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){
 308        cerr<<":"<<"("<<(NI->element->getElement())
 309          ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")";
 310      }
 311      cerr<<"--------\n";
 312    }
 313 }
 314
 315
 316 //get a list of nodes in the graph
 317 //in r-topological sorted order
 318 //note that we assumed graph to be connected
 319 list<Node *> Graph::reverseTopologicalSort() const{
 320   list <Node *> toReturn;
 321   list<Node *> lt=getAllNodes();
 322   for(list<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
 323     if((*LI)->getWeight()!=GREY && (*LI)->getWeight()!=BLACK)
 324       DFS_Visit(*LI, toReturn);
 325   }
 326   return toReturn;
 327 }
 328
 329 //a private method for doing DFS traversal of graph
 330 //this is used in determining the reverse topological sort
 331 //of the graph
 332 void Graph::DFS_Visit(Node *nd, list<Node *> &toReturn) const {
 333   nd->setWeight(GREY);
 334   list<Node *> lt=getSuccNodes(nd);
 335   for(list<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
 336     if((*LI)->getWeight()!=GREY && (*LI)->getWeight()!=BLACK)
 337       DFS_Visit(*LI, toReturn);
 338   }
 339   toReturn.push_back(nd);
 340 }
 341
 342 //Ordinarily, the graph is directional
 343 //this converts the graph into an
 344 //undirectional graph
 345 //This is done by adding an edge
 346 //v->u for all existing edges u->v
 347 void Graph::makeUnDirectional(){
 348   list<Node* > allNodes=getAllNodes();
 349   for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 350       ++NI) {
 351     nodeList nl=getNodeList(*NI);
 352     for(nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE; ++NLI){
 353       Edge ed(NLI->element, *NI, NLI->weight);
 354       if(!hasEdgeAndWt(ed)){
 355 #ifdef DEBUG_PATH_PROFILES
 356         cerr<<"######doesn't hv\n";
 357         printEdge(ed);
 358 #endif
 359         addEdgeForce(ed);
 360       }
 361     }
 362   }
 363 }
 364
 365 //reverse the sign of weights on edges
 366 //this way, max-spanning tree could be obtained
 367 //usin min-spanning tree, and vice versa
 368 void Graph::reverseWts(){
 369   list<Node *> allNodes=getAllNodes();
 370   for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 371       ++NI) {
 372     nodeList node_list=getNodeList(*NI);
 373     for(nodeList::iterator NLI=nodes[*NI].begin(), NLE=nodes[*NI].end();
 374         NLI!=NLE; ++NLI)
 375       NLI->weight=-NLI->weight;
 376   }
 377 }
 378
 379
 380 //getting the backedges in a graph
 381 //Its a variation of DFS to get the backedges in the graph
 382 //We get back edges by associating a time
 383 //and a color with each vertex.
 384 //The time of a vertex is the time when it was first visited
 385 //The color of a vertex is initially WHITE,
 386 //Changes to GREY when it is first visited,
 387 //and changes to BLACK when ALL its neighbors
 388 //have been visited
 389 //So we have a back edge when we meet a successor of
 390 //a node with smaller time, and GREY color
 391 void Graph::getBackEdges(vector<Edge > &be) const{
 392   map<Node *, Color > color;
 393   map<Node *, int > d;
 394   list<Node *> allNodes=getAllNodes();
 395   int time=0;
 396   for(list<Node *>::const_iterator NI=allNodes.begin(), NE=allNodes.end();
 397       NI!=NE; ++NI){
 398     if(color[*NI]!=GREY && color[*NI]!=BLACK)
 399       getBackEdgesVisit(*NI, be, color, d, time);
 400   }
 401 }
 402
 403 //helper function to get back edges: it is called by
 404 //the "getBackEdges" function above
 405 void Graph::getBackEdgesVisit(Node *u, vector<Edge > &be,
 406                               map<Node *, Color > &color,
 407                               map<Node *, int > &d, int &time) const{
 408   color[u]=GREY;
 409   time++;
 410   d[u]=time;
 411   list<Node *> succ_list=getSuccNodes(u);
 412
 413   for(list<Node *>::const_iterator v=succ_list.begin(), ve=succ_list.end();
 414       v!=ve; ++v){
 415     if(color[*v]!=GREY && color[*v]!=BLACK){
 416       getBackEdgesVisit(*v, be, color, d, time);
 417     }
 418
 419     //now checking for d and f vals
 420     if(color[*v]==GREY){
 421       //so v is ancestor of u if time of u > time of v
 422       if(d[u] >= d[*v]){
 423         Edge *ed=new Edge(u, *v);
 424         if (!(*u == *getExit() && **v == *getRoot()))
 425           be.push_back(*ed);      // choose the forward edges
 426       }
 427     }
 428   }
 429   color[u]=BLACK;//done with visiting the node and its neighbors
 430 }
 431
 432