lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp

   1 //===-- Graph.cpp - Implements Graph class --------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements Graph for helping in trace generation This graph gets used by
  11 // "ProfilePaths" class.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "Graph.h"
  16 #include "llvm/iTerminators.h"
  17 #include "Support/Debug.h"
  18 #include <algorithm>
  19
  20 using std::vector;
  21
  22 const graphListElement *findNodeInList(const Graph::nodeList &NL,
  23                                               Node *N) {
  24   for(Graph::nodeList::const_iterator NI = NL.begin(), NE=NL.end(); NI != NE;
  25       ++NI)
  26     if (*NI->element== *N)
  27       return &*NI;
  28   return 0;
  29 }
  30
  31 graphListElement *findNodeInList(Graph::nodeList &NL, Node *N) {
  32   for(Graph::nodeList::iterator NI = NL.begin(), NE=NL.end(); NI != NE; ++NI)
  33     if (*NI->element== *N)
  34       return &*NI;
  35   return 0;
  36 }
  37
  38 //graph constructor with root and exit specified
  39 Graph::Graph(std::vector<Node*> n, std::vector<Edge> e,
  40              Node *rt, Node *lt){
  41   strt=rt;
  42   ext=lt;
  43   for(vector<Node* >::iterator x=n.begin(), en=n.end(); x!=en; ++x)
  44     //nodes[*x] = list<graphListElement>();
  45     nodes[*x] = vector<graphListElement>();
  46
  47   for(vector<Edge >::iterator x=e.begin(), en=e.end(); x!=en; ++x){
  48     Edge ee=*x;
  49     int w=ee.getWeight();
  50     //nodes[ee.getFirst()].push_front(graphListElement(ee.getSecond(),w, ee.getRandId()));
  51     nodes[ee.getFirst()].push_back(graphListElement(ee.getSecond(),w, ee.getRandId()));
  52   }
  53
  54 }
  55
  56 //sorting edgelist, called by backEdgeVist ONLY!!!
  57 Graph::nodeList &Graph::sortNodeList(Node *par, nodeList &nl, vector<Edge> &be){
  58   assert(par && "null node pointer");
  59   BasicBlock *bbPar = par->getElement();
  60
  61   if(nl.size()<=1) return nl;
  62   if(getExit() == par) return nl;
  63
  64   for(nodeList::iterator NLI = nl.begin(), NLE = nl.end()-1; NLI != NLE; ++NLI){
  65     nodeList::iterator min = NLI;
  66     for(nodeList::iterator LI = NLI+1, LE = nl.end(); LI!=LE; ++LI){
  67       //if LI < min, min = LI
  68       if(min->element->getElement() == LI->element->getElement() &&
  69          min->element == getExit()){
  70
  71         //same successors: so might be exit???
  72         //if it is exit, then see which is backedge
  73         //check if LI is a left back edge!
  74
  75         TerminatorInst *tti = par->getElement()->getTerminator();
  76         BranchInst *ti =  cast<BranchInst>(tti);
  77
  78         assert(ti && "not a branch");
  79         assert(ti->getNumSuccessors()==2 && "less successors!");
  80
  81         BasicBlock *tB = ti->getSuccessor(0);
  82         BasicBlock *fB = ti->getSuccessor(1);
  83         //so one of LI or min must be back edge!
  84         //Algo: if succ(0)!=LI (and so !=min) then succ(0) is backedge
  85         //and then see which of min or LI is backedge
  86         //THEN if LI is in be, then min=LI
  87         if(LI->element->getElement() != tB){//so backedge must be made min!
  88           for(vector<Edge>::iterator VBEI = be.begin(), VBEE = be.end();
  89               VBEI != VBEE; ++VBEI){
  90             if(VBEI->getRandId() == LI->randId){
  91               min = LI;
  92               break;
  93             }
  94             else if(VBEI->getRandId() == min->randId)
  95               break;
  96           }
  97         }
  98         else{// if(LI->element->getElement() != fB)
  99           for(vector<Edge>::iterator VBEI = be.begin(), VBEE = be.end();
 100               VBEI != VBEE; ++VBEI){
 101             if(VBEI->getRandId() == min->randId){
 102               min = LI;
 103               break;
 104             }
 105             else if(VBEI->getRandId() == LI->randId)
 106               break;
 107           }
 108         }
 109       }
 110
 111       else if (min->element->getElement() != LI->element->getElement()){
 112         TerminatorInst *tti = par->getElement()->getTerminator();
 113         BranchInst *ti =  cast<BranchInst>(tti);
 114         assert(ti && "not a branch");
 115
 116         if(ti->getNumSuccessors()<=1) continue;
 117
 118         assert(ti->getNumSuccessors()==2 && "less successors!");
 119
 120         BasicBlock *tB = ti->getSuccessor(0);
 121         BasicBlock *fB = ti->getSuccessor(1);
 122
 123         if(tB == LI->element->getElement() || fB == min->element->getElement())
 124           min = LI;
 125       }
 126     }
 127
 128     graphListElement tmpElmnt = *min;
 129     *min = *NLI;
 130     *NLI = tmpElmnt;
 131   }
 132   return nl;
 133 }
 134
 135 //check whether graph has an edge
 136 //having an edge simply means that there is an edge in the graph
 137 //which has same endpoints as the given edge
 138 bool Graph::hasEdge(Edge ed){
 139   if(ed.isNull())
 140     return false;
 141
 142   nodeList &nli= nodes[ed.getFirst()]; //getNodeList(ed.getFirst());
 143   Node *nd2=ed.getSecond();
 144
 145   return (findNodeInList(nli,nd2)!=NULL);
 146
 147 }
 148
 149
 150 //check whether graph has an edge, with a given wt
 151 //having an edge simply means that there is an edge in the graph
 152 //which has same endpoints as the given edge
 153 //This function checks, moreover, that the wt of edge matches too
 154 bool Graph::hasEdgeAndWt(Edge ed){
 155   if(ed.isNull())
 156     return false;
 157
 158   Node *nd2=ed.getSecond();
 159   nodeList &nli = nodes[ed.getFirst()];//getNodeList(ed.getFirst());
 160
 161   for(nodeList::iterator NI=nli.begin(), NE=nli.end(); NI!=NE; ++NI)
 162     if(*NI->element == *nd2 && ed.getWeight()==NI->weight)
 163       return true;
 164
 165   return false;
 166 }
 167
 168 //add a node
 169 void Graph::addNode(Node *nd){
 170   vector<Node *> lt=getAllNodes();
 171
 172   for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE;++LI){
 173     if(**LI==*nd)
 174       return;
 175   }
 176   //chng
 177   nodes[nd] =vector<graphListElement>(); //list<graphListElement>();
 178 }
 179
 180 //add an edge
 181 //this adds an edge ONLY when
 182 //the edge to be added does not already exist
 183 //we "equate" two edges here only with their
 184 //end points
 185 void Graph::addEdge(Edge ed, int w){
 186   nodeList &ndList = nodes[ed.getFirst()];
 187   Node *nd2=ed.getSecond();
 188
 189   if(findNodeInList(nodes[ed.getFirst()], nd2))
 190     return;
 191
 192   //ndList.push_front(graphListElement(nd2,w, ed.getRandId()));
 193   ndList.push_back(graphListElement(nd2,w, ed.getRandId()));//chng
 194   //sortNodeList(ed.getFirst(), ndList);
 195
 196   //sort(ndList.begin(), ndList.end(), NodeListSort());
 197 }
 198
 199 //add an edge EVEN IF such an edge already exists
 200 //this may make a multi-graph
 201 //which does happen when we add dummy edges
 202 //to the graph, for compensating for back-edges
 203 void Graph::addEdgeForce(Edge ed){
 204   //nodes[ed.getFirst()].push_front(graphListElement(ed.getSecond(),
 205   //ed.getWeight(), ed.getRandId()));
 206   nodes[ed.getFirst()].push_back
 207     (graphListElement(ed.getSecond(), ed.getWeight(), ed.getRandId()));
 208
 209   //sortNodeList(ed.getFirst(), nodes[ed.getFirst()]);
 210   //sort(nodes[ed.getFirst()].begin(), nodes[ed.getFirst()].end(), NodeListSort());
 211 }
 212
 213 //remove an edge
 214 //Note that it removes just one edge,
 215 //the first edge that is encountered
 216 void Graph::removeEdge(Edge ed){
 217   nodeList &ndList = nodes[ed.getFirst()];
 218   Node &nd2 = *ed.getSecond();
 219
 220   for(nodeList::iterator NI=ndList.begin(), NE=ndList.end(); NI!=NE ;++NI) {
 221     if(*NI->element == nd2) {
 222       ndList.erase(NI);
 223       break;
 224     }
 225   }
 226 }
 227
 228 //remove an edge with a given wt
 229 //Note that it removes just one edge,
 230 //the first edge that is encountered
 231 void Graph::removeEdgeWithWt(Edge ed){
 232   nodeList &ndList = nodes[ed.getFirst()];
 233   Node &nd2 = *ed.getSecond();
 234
 235   for(nodeList::iterator NI=ndList.begin(), NE=ndList.end(); NI!=NE ;++NI) {
 236     if(*NI->element == nd2 && NI->weight==ed.getWeight()) {
 237       ndList.erase(NI);
 238       break;
 239     }
 240   }
 241 }
 242
 243 //set the weight of an edge
 244 void Graph::setWeight(Edge ed){
 245   graphListElement *El = findNodeInList(nodes[ed.getFirst()], ed.getSecond());
 246   if (El)
 247     El->weight=ed.getWeight();
 248 }
 249
 250
 251
 252 //get the list of successor nodes
 253 vector<Node *> Graph::getSuccNodes(Node *nd){
 254   nodeMapTy::const_iterator nli = nodes.find(nd);
 255   assert(nli != nodes.end() && "Node must be in nodes map");
 256   const nodeList &nl = getNodeList(nd);//getSortedNodeList(nd);
 257
 258   vector<Node *> lt;
 259   for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI)
 260     lt.push_back(NI->element);
 261
 262   return lt;
 263 }
 264
 265 //get the number of outgoing edges
 266 int Graph::getNumberOfOutgoingEdges(Node *nd) const {
 267   nodeMapTy::const_iterator nli = nodes.find(nd);
 268   assert(nli != nodes.end() && "Node must be in nodes map");
 269   const nodeList &nl = nli->second;
 270
 271   int count=0;
 272   for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI)
 273     count++;
 274
 275   return count;
 276 }
 277
 278 //get the list of predecessor nodes
 279 vector<Node *> Graph::getPredNodes(Node *nd){
 280   vector<Node *> lt;
 281   for(nodeMapTy::const_iterator EI=nodes.begin(), EE=nodes.end(); EI!=EE ;++EI){
 282     Node *lnode=EI->first;
 283     const nodeList &nl = getNodeList(lnode);
 284
 285     const graphListElement *N = findNodeInList(nl, nd);
 286     if (N) lt.push_back(lnode);
 287   }
 288   return lt;
 289 }
 290
 291 //get the number of predecessor nodes
 292 int Graph::getNumberOfIncomingEdges(Node *nd){
 293   int count=0;
 294   for(nodeMapTy::const_iterator EI=nodes.begin(), EE=nodes.end(); EI!=EE ;++EI){
 295     Node *lnode=EI->first;
 296     const nodeList &nl = getNodeList(lnode);
 297     for(Graph::nodeList::const_iterator NI = nl.begin(), NE=nl.end(); NI != NE;
 298         ++NI)
 299       if (*NI->element== *nd)
 300         count++;
 301   }
 302   return count;
 303 }
 304
 305 //get the list of all the vertices in graph
 306 vector<Node *> Graph::getAllNodes() const{
 307   vector<Node *> lt;
 308   for(nodeMapTy::const_iterator x=nodes.begin(), en=nodes.end(); x != en; ++x)
 309     lt.push_back(x->first);
 310
 311   return lt;
 312 }
 313
 314 //get the list of all the vertices in graph
 315 vector<Node *> Graph::getAllNodes(){
 316   vector<Node *> lt;
 317   for(nodeMapTy::const_iterator x=nodes.begin(), en=nodes.end(); x != en; ++x)
 318     lt.push_back(x->first);
 319
 320   return lt;
 321 }
 322
 323 //class to compare two nodes in graph
 324 //based on their wt: this is used in
 325 //finding the maximal spanning tree
 326 struct compare_nodes {
 327   bool operator()(Node *n1, Node *n2){
 328     return n1->getWeight() < n2->getWeight();
 329   }
 330 };
 331
 332
 333 static void printNode(Node *nd){
 334   std::cerr<<"Node:"<<nd->getElement()->getName()<<"\n";
 335 }
 336
 337 //Get the Maximal spanning tree (also a graph)
 338 //of the graph
 339 Graph* Graph::getMaxSpanningTree(){
 340   //assume connected graph
 341
 342   Graph *st=new Graph();//max spanning tree, undirected edges
 343   int inf=9999999;//largest key
 344   vector<Node *> lt = getAllNodes();
 345
 346   //initially put all vertices in vector vt
 347   //assign wt(root)=0
 348   //wt(others)=infinity
 349   //
 350   //now:
 351   //pull out u: a vertex frm vt of min wt
 352   //for all vertices w in vt,
 353   //if wt(w) greater than
 354   //the wt(u->w), then assign
 355   //wt(w) to be wt(u->w).
 356   //
 357   //make parent(u)=w in the spanning tree
 358   //keep pulling out vertices from vt till it is empty
 359
 360   vector<Node *> vt;
 361
 362   std::map<Node*, Node* > parent;
 363   std::map<Node*, int > ed_weight;
 364
 365   //initialize: wt(root)=0, wt(others)=infinity
 366   //parent(root)=NULL, parent(others) not defined (but not null)
 367   for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
 368     Node *thisNode=*LI;
 369     if(*thisNode == *getRoot()){
 370       thisNode->setWeight(0);
 371       parent[thisNode]=NULL;
 372       ed_weight[thisNode]=0;
 373     }
 374     else{
 375       thisNode->setWeight(inf);
 376     }
 377     st->addNode(thisNode);//add all nodes to spanning tree
 378     //we later need to assign edges in the tree
 379     vt.push_back(thisNode); //pushed all nodes in vt
 380   }
 381
 382   //keep pulling out vertex of min wt from vt
 383   while(!vt.empty()){
 384     Node *u=*(min_element(vt.begin(), vt.end(), compare_nodes()));
 385     DEBUG(std::cerr<<"popped wt"<<(u)->getWeight()<<"\n";
 386           printNode(u));
 387
 388     if(parent[u]!=NULL){ //so not root
 389       Edge edge(parent[u],u, ed_weight[u]); //assign edge in spanning tree
 390       st->addEdge(edge,ed_weight[u]);
 391
 392       DEBUG(std::cerr<<"added:\n";
 393             printEdge(edge));
 394     }
 395
 396     //vt.erase(u);
 397
 398     //remove u frm vt
 399     for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){
 400       if(**VI==*u){
 401         vt.erase(VI);
 402         break;
 403       }
 404     }
 405
 406     //assign wt(v) to all adjacent vertices v of u
 407     //only if v is in vt
 408     Graph::nodeList &nl = getNodeList(u);
 409     for(nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){
 410       Node *v=NI->element;
 411       int weight=-NI->weight;
 412       //check if v is in vt
 413       bool contains=false;
 414       for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){
 415         if(**VI==*v){
 416           contains=true;
 417           break;
 418         }
 419       }
 420       DEBUG(std::cerr<<"wt:v->wt"<<weight<<":"<<v->getWeight()<<"\n";
 421             printNode(v);std::cerr<<"node wt:"<<(*v).weight<<"\n");
 422
 423       //so if v in in vt, change wt(v) to wt(u->v)
 424       //only if wt(u->v)<wt(v)
 425       if(contains && weight<v->getWeight()){
 426         parent[v]=u;
 427         ed_weight[v]=weight;
 428         v->setWeight(weight);
 429
 430         DEBUG(std::cerr<<v->getWeight()<<":Set weight------\n";
 431               printGraph();
 432               printEdge(Edge(u,v,weight)));
 433       }
 434     }
 435   }
 436   return st;
 437 }
 438
 439 //print the graph (for debugging)
 440 void Graph::printGraph(){
 441    vector<Node *> lt=getAllNodes();
 442    std::cerr<<"Graph---------------------\n";
 443    for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
 444      std::cerr<<((*LI)->getElement())->getName()<<"->";
 445      Graph::nodeList &nl = getNodeList(*LI);
 446      for(Graph::nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){
 447        std::cerr<<":"<<"("<<(NI->element->getElement())
 448          ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")";
 449      }
 450      std::cerr<<"--------\n";
 451    }
 452 }
 453
 454
 455 //get a list of nodes in the graph
 456 //in r-topological sorted order
 457 //note that we assumed graph to be connected
 458 vector<Node *> Graph::reverseTopologicalSort(){
 459   vector <Node *> toReturn;
 460   vector<Node *> lt=getAllNodes();
 461   for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
 462     if((*LI)->getWeight()!=GREY && (*LI)->getWeight()!=BLACK)
 463       DFS_Visit(*LI, toReturn);
 464   }
 465
 466   return toReturn;
 467 }
 468
 469 //a private method for doing DFS traversal of graph
 470 //this is used in determining the reverse topological sort
 471 //of the graph
 472 void Graph::DFS_Visit(Node *nd, vector<Node *> &toReturn){
 473   nd->setWeight(GREY);
 474   vector<Node *> lt=getSuccNodes(nd);
 475   for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
 476     if((*LI)->getWeight()!=GREY && (*LI)->getWeight()!=BLACK)
 477       DFS_Visit(*LI, toReturn);
 478   }
 479   toReturn.push_back(nd);
 480 }
 481
 482 //Ordinarily, the graph is directional
 483 //this converts the graph into an
 484 //undirectional graph
 485 //This is done by adding an edge
 486 //v->u for all existing edges u->v
 487 void Graph::makeUnDirectional(){
 488   vector<Node* > allNodes=getAllNodes();
 489   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 490       ++NI) {
 491     nodeList &nl = getNodeList(*NI);
 492     for(nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE; ++NLI){
 493       Edge ed(NLI->element, *NI, NLI->weight);
 494       if(!hasEdgeAndWt(ed)){
 495         DEBUG(std::cerr<<"######doesn't hv\n";
 496               printEdge(ed));
 497         addEdgeForce(ed);
 498       }
 499     }
 500   }
 501 }
 502
 503 //reverse the sign of weights on edges
 504 //this way, max-spanning tree could be obtained
 505 //using min-spanning tree, and vice versa
 506 void Graph::reverseWts(){
 507   vector<Node *> allNodes=getAllNodes();
 508   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 509       ++NI) {
 510     nodeList &node_list = getNodeList(*NI);
 511     for(nodeList::iterator NLI=nodes[*NI].begin(), NLE=nodes[*NI].end();
 512         NLI!=NLE; ++NLI)
 513       NLI->weight=-NLI->weight;
 514   }
 515 }
 516
 517
 518 //getting the backedges in a graph
 519 //Its a variation of DFS to get the backedges in the graph
 520 //We get back edges by associating a time
 521 //and a color with each vertex.
 522 //The time of a vertex is the time when it was first visited
 523 //The color of a vertex is initially WHITE,
 524 //Changes to GREY when it is first visited,
 525 //and changes to BLACK when ALL its neighbors
 526 //have been visited
 527 //So we have a back edge when we meet a successor of
 528 //a node with smaller time, and GREY color
 529 void Graph::getBackEdges(vector<Edge > &be, std::map<Node *, int> &d){
 530   std::map<Node *, Color > color;
 531   int time=0;
 532
 533   getBackEdgesVisit(getRoot(), be, color, d, time);
 534 }
 535
 536 //helper function to get back edges: it is called by
 537 //the "getBackEdges" function above
 538 void Graph::getBackEdgesVisit(Node *u, vector<Edge > &be,
 539                               std::map<Node *, Color > &color,
 540                               std::map<Node *, int > &d, int &time) {
 541   color[u]=GREY;
 542   time++;
 543   d[u]=time;
 544
 545   vector<graphListElement> &succ_list = getNodeList(u);
 546
 547   for(vector<graphListElement>::iterator vl=succ_list.begin(),
 548         ve=succ_list.end(); vl!=ve; ++vl){
 549     Node *v=vl->element;
 550     if(color[v]!=GREY && color[v]!=BLACK){
 551       getBackEdgesVisit(v, be, color, d, time);
 552     }
 553
 554     //now checking for d and f vals
 555     if(color[v]==GREY){
 556       //so v is ancestor of u if time of u > time of v
 557       if(d[u] >= d[v]){
 558         Edge *ed=new Edge(u, v,vl->weight, vl->randId);
 559         if (!(*u == *getExit() && *v == *getRoot()))
 560           be.push_back(*ed);      // choose the forward edges
 561       }
 562     }
 563   }
 564   color[u]=BLACK;//done with visiting the node and its neighbors
 565 }
 566
 567