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