LLVM API Documentation
00001 //===-- Graph.cpp - Implements Graph class --------------------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This implements Graph for helping in trace generation This graph gets used by 00011 // "ProfilePaths" class. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "Graph.h" 00016 #include "llvm/Instructions.h" 00017 #include "llvm/Support/Debug.h" 00018 #include <algorithm> 00019 00020 using std::vector; 00021 00022 namespace llvm { 00023 00024 const graphListElement *findNodeInList(const Graph::nodeList &NL, 00025 Node *N) { 00026 for(Graph::nodeList::const_iterator NI = NL.begin(), NE=NL.end(); NI != NE; 00027 ++NI) 00028 if (*NI->element== *N) 00029 return &*NI; 00030 return 0; 00031 } 00032 00033 graphListElement *findNodeInList(Graph::nodeList &NL, Node *N) { 00034 for(Graph::nodeList::iterator NI = NL.begin(), NE=NL.end(); NI != NE; ++NI) 00035 if (*NI->element== *N) 00036 return &*NI; 00037 return 0; 00038 } 00039 00040 //graph constructor with root and exit specified 00041 Graph::Graph(std::vector<Node*> n, std::vector<Edge> e, 00042 Node *rt, Node *lt){ 00043 strt=rt; 00044 ext=lt; 00045 for(vector<Node* >::iterator x=n.begin(), en=n.end(); x!=en; ++x) 00046 //nodes[*x] = list<graphListElement>(); 00047 nodes[*x] = vector<graphListElement>(); 00048 00049 for(vector<Edge >::iterator x=e.begin(), en=e.end(); x!=en; ++x){ 00050 Edge ee=*x; 00051 int w=ee.getWeight(); 00052 //nodes[ee.getFirst()].push_front(graphListElement(ee.getSecond(),w, ee.getRandId())); 00053 nodes[ee.getFirst()].push_back(graphListElement(ee.getSecond(),w, ee.getRandId())); 00054 } 00055 00056 } 00057 00058 //sorting edgelist, called by backEdgeVist ONLY!!! 00059 Graph::nodeList &Graph::sortNodeList(Node *par, nodeList &nl, vector<Edge> &be){ 00060 assert(par && "null node pointer"); 00061 BasicBlock *bbPar = par->getElement(); 00062 00063 if(nl.size()<=1) return nl; 00064 if(getExit() == par) return nl; 00065 00066 for(nodeList::iterator NLI = nl.begin(), NLE = nl.end()-1; NLI != NLE; ++NLI){ 00067 nodeList::iterator min = NLI; 00068 for(nodeList::iterator LI = NLI+1, LE = nl.end(); LI!=LE; ++LI){ 00069 //if LI < min, min = LI 00070 if(min->element->getElement() == LI->element->getElement() && 00071 min->element == getExit()){ 00072 00073 //same successors: so might be exit??? 00074 //if it is exit, then see which is backedge 00075 //check if LI is a left back edge! 00076 00077 TerminatorInst *tti = par->getElement()->getTerminator(); 00078 BranchInst *ti = cast<BranchInst>(tti); 00079 00080 assert(ti && "not a branch"); 00081 assert(ti->getNumSuccessors()==2 && "less successors!"); 00082 00083 BasicBlock *tB = ti->getSuccessor(0); 00084 BasicBlock *fB = ti->getSuccessor(1); 00085 //so one of LI or min must be back edge! 00086 //Algo: if succ(0)!=LI (and so !=min) then succ(0) is backedge 00087 //and then see which of min or LI is backedge 00088 //THEN if LI is in be, then min=LI 00089 if(LI->element->getElement() != tB){//so backedge must be made min! 00090 for(vector<Edge>::iterator VBEI = be.begin(), VBEE = be.end(); 00091 VBEI != VBEE; ++VBEI){ 00092 if(VBEI->getRandId() == LI->randId){ 00093 min = LI; 00094 break; 00095 } 00096 else if(VBEI->getRandId() == min->randId) 00097 break; 00098 } 00099 } 00100 else{// if(LI->element->getElement() != fB) 00101 for(vector<Edge>::iterator VBEI = be.begin(), VBEE = be.end(); 00102 VBEI != VBEE; ++VBEI){ 00103 if(VBEI->getRandId() == min->randId){ 00104 min = LI; 00105 break; 00106 } 00107 else if(VBEI->getRandId() == LI->randId) 00108 break; 00109 } 00110 } 00111 } 00112 00113 else if (min->element->getElement() != LI->element->getElement()){ 00114 TerminatorInst *tti = par->getElement()->getTerminator(); 00115 BranchInst *ti = cast<BranchInst>(tti); 00116 assert(ti && "not a branch"); 00117 00118 if(ti->getNumSuccessors()<=1) continue; 00119 00120 assert(ti->getNumSuccessors()==2 && "less successors!"); 00121 00122 BasicBlock *tB = ti->getSuccessor(0); 00123 BasicBlock *fB = ti->getSuccessor(1); 00124 00125 if(tB == LI->element->getElement() || fB == min->element->getElement()) 00126 min = LI; 00127 } 00128 } 00129 00130 graphListElement tmpElmnt = *min; 00131 *min = *NLI; 00132 *NLI = tmpElmnt; 00133 } 00134 return nl; 00135 } 00136 00137 //check whether graph has an edge 00138 //having an edge simply means that there is an edge in the graph 00139 //which has same endpoints as the given edge 00140 bool Graph::hasEdge(Edge ed){ 00141 if(ed.isNull()) 00142 return false; 00143 00144 nodeList &nli= nodes[ed.getFirst()]; //getNodeList(ed.getFirst()); 00145 Node *nd2=ed.getSecond(); 00146 00147 return (findNodeInList(nli,nd2)!=NULL); 00148 00149 } 00150 00151 00152 //check whether graph has an edge, with a given wt 00153 //having an edge simply means that there is an edge in the graph 00154 //which has same endpoints as the given edge 00155 //This function checks, moreover, that the wt of edge matches too 00156 bool Graph::hasEdgeAndWt(Edge ed){ 00157 if(ed.isNull()) 00158 return false; 00159 00160 Node *nd2=ed.getSecond(); 00161 nodeList &nli = nodes[ed.getFirst()];//getNodeList(ed.getFirst()); 00162 00163 for(nodeList::iterator NI=nli.begin(), NE=nli.end(); NI!=NE; ++NI) 00164 if(*NI->element == *nd2 && ed.getWeight()==NI->weight) 00165 return true; 00166 00167 return false; 00168 } 00169 00170 //add a node 00171 void Graph::addNode(Node *nd){ 00172 vector<Node *> lt=getAllNodes(); 00173 00174 for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE;++LI){ 00175 if(**LI==*nd) 00176 return; 00177 } 00178 //chng 00179 nodes[nd] =vector<graphListElement>(); //list<graphListElement>(); 00180 } 00181 00182 //add an edge 00183 //this adds an edge ONLY when 00184 //the edge to be added does not already exist 00185 //we "equate" two edges here only with their 00186 //end points 00187 void Graph::addEdge(Edge ed, int w){ 00188 nodeList &ndList = nodes[ed.getFirst()]; 00189 Node *nd2=ed.getSecond(); 00190 00191 if(findNodeInList(nodes[ed.getFirst()], nd2)) 00192 return; 00193 00194 //ndList.push_front(graphListElement(nd2,w, ed.getRandId())); 00195 ndList.push_back(graphListElement(nd2,w, ed.getRandId()));//chng 00196 //sortNodeList(ed.getFirst(), ndList); 00197 00198 //sort(ndList.begin(), ndList.end(), NodeListSort()); 00199 } 00200 00201 //add an edge EVEN IF such an edge already exists 00202 //this may make a multi-graph 00203 //which does happen when we add dummy edges 00204 //to the graph, for compensating for back-edges 00205 void Graph::addEdgeForce(Edge ed){ 00206 //nodes[ed.getFirst()].push_front(graphListElement(ed.getSecond(), 00207 //ed.getWeight(), ed.getRandId())); 00208 nodes[ed.getFirst()].push_back 00209 (graphListElement(ed.getSecond(), ed.getWeight(), ed.getRandId())); 00210 00211 //sortNodeList(ed.getFirst(), nodes[ed.getFirst()]); 00212 //sort(nodes[ed.getFirst()].begin(), nodes[ed.getFirst()].end(), NodeListSort()); 00213 } 00214 00215 //remove an edge 00216 //Note that it removes just one edge, 00217 //the first edge that is encountered 00218 void Graph::removeEdge(Edge ed){ 00219 nodeList &ndList = nodes[ed.getFirst()]; 00220 Node &nd2 = *ed.getSecond(); 00221 00222 for(nodeList::iterator NI=ndList.begin(), NE=ndList.end(); NI!=NE ;++NI) { 00223 if(*NI->element == nd2) { 00224 ndList.erase(NI); 00225 break; 00226 } 00227 } 00228 } 00229 00230 //remove an edge with a given wt 00231 //Note that it removes just one edge, 00232 //the first edge that is encountered 00233 void Graph::removeEdgeWithWt(Edge ed){ 00234 nodeList &ndList = nodes[ed.getFirst()]; 00235 Node &nd2 = *ed.getSecond(); 00236 00237 for(nodeList::iterator NI=ndList.begin(), NE=ndList.end(); NI!=NE ;++NI) { 00238 if(*NI->element == nd2 && NI->weight==ed.getWeight()) { 00239 ndList.erase(NI); 00240 break; 00241 } 00242 } 00243 } 00244 00245 //set the weight of an edge 00246 void Graph::setWeight(Edge ed){ 00247 graphListElement *El = findNodeInList(nodes[ed.getFirst()], ed.getSecond()); 00248 if (El) 00249 El->weight=ed.getWeight(); 00250 } 00251 00252 00253 00254 //get the list of successor nodes 00255 vector<Node *> Graph::getSuccNodes(Node *nd){ 00256 nodeMapTy::const_iterator nli = nodes.find(nd); 00257 assert(nli != nodes.end() && "Node must be in nodes map"); 00258 const nodeList &nl = getNodeList(nd);//getSortedNodeList(nd); 00259 00260 vector<Node *> lt; 00261 for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI) 00262 lt.push_back(NI->element); 00263 00264 return lt; 00265 } 00266 00267 //get the number of outgoing edges 00268 int Graph::getNumberOfOutgoingEdges(Node *nd) const { 00269 nodeMapTy::const_iterator nli = nodes.find(nd); 00270 assert(nli != nodes.end() && "Node must be in nodes map"); 00271 const nodeList &nl = nli->second; 00272 00273 int count=0; 00274 for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI) 00275 count++; 00276 00277 return count; 00278 } 00279 00280 //get the list of predecessor nodes 00281 vector<Node *> Graph::getPredNodes(Node *nd){ 00282 vector<Node *> lt; 00283 for(nodeMapTy::const_iterator EI=nodes.begin(), EE=nodes.end(); EI!=EE ;++EI){ 00284 Node *lnode=EI->first; 00285 const nodeList &nl = getNodeList(lnode); 00286 00287 const graphListElement *N = findNodeInList(nl, nd); 00288 if (N) lt.push_back(lnode); 00289 } 00290 return lt; 00291 } 00292 00293 //get the number of predecessor nodes 00294 int Graph::getNumberOfIncomingEdges(Node *nd){ 00295 int count=0; 00296 for(nodeMapTy::const_iterator EI=nodes.begin(), EE=nodes.end(); EI!=EE ;++EI){ 00297 Node *lnode=EI->first; 00298 const nodeList &nl = getNodeList(lnode); 00299 for(Graph::nodeList::const_iterator NI = nl.begin(), NE=nl.end(); NI != NE; 00300 ++NI) 00301 if (*NI->element== *nd) 00302 count++; 00303 } 00304 return count; 00305 } 00306 00307 //get the list of all the vertices in graph 00308 vector<Node *> Graph::getAllNodes() const{ 00309 vector<Node *> lt; 00310 for(nodeMapTy::const_iterator x=nodes.begin(), en=nodes.end(); x != en; ++x) 00311 lt.push_back(x->first); 00312 00313 return lt; 00314 } 00315 00316 //get the list of all the vertices in graph 00317 vector<Node *> Graph::getAllNodes(){ 00318 vector<Node *> lt; 00319 for(nodeMapTy::const_iterator x=nodes.begin(), en=nodes.end(); x != en; ++x) 00320 lt.push_back(x->first); 00321 00322 return lt; 00323 } 00324 00325 //class to compare two nodes in graph 00326 //based on their wt: this is used in 00327 //finding the maximal spanning tree 00328 struct compare_nodes { 00329 bool operator()(Node *n1, Node *n2){ 00330 return n1->getWeight() < n2->getWeight(); 00331 } 00332 }; 00333 00334 00335 static void printNode(Node *nd){ 00336 std::cerr<<"Node:"<<nd->getElement()->getName()<<"\n"; 00337 } 00338 00339 //Get the Maximal spanning tree (also a graph) 00340 //of the graph 00341 Graph* Graph::getMaxSpanningTree(){ 00342 //assume connected graph 00343 00344 Graph *st=new Graph();//max spanning tree, undirected edges 00345 int inf=9999999;//largest key 00346 vector<Node *> lt = getAllNodes(); 00347 00348 //initially put all vertices in vector vt 00349 //assign wt(root)=0 00350 //wt(others)=infinity 00351 // 00352 //now: 00353 //pull out u: a vertex frm vt of min wt 00354 //for all vertices w in vt, 00355 //if wt(w) greater than 00356 //the wt(u->w), then assign 00357 //wt(w) to be wt(u->w). 00358 // 00359 //make parent(u)=w in the spanning tree 00360 //keep pulling out vertices from vt till it is empty 00361 00362 vector<Node *> vt; 00363 00364 std::map<Node*, Node* > parent; 00365 std::map<Node*, int > ed_weight; 00366 00367 //initialize: wt(root)=0, wt(others)=infinity 00368 //parent(root)=NULL, parent(others) not defined (but not null) 00369 for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){ 00370 Node *thisNode=*LI; 00371 if(*thisNode == *getRoot()){ 00372 thisNode->setWeight(0); 00373 parent[thisNode]=NULL; 00374 ed_weight[thisNode]=0; 00375 } 00376 else{ 00377 thisNode->setWeight(inf); 00378 } 00379 st->addNode(thisNode);//add all nodes to spanning tree 00380 //we later need to assign edges in the tree 00381 vt.push_back(thisNode); //pushed all nodes in vt 00382 } 00383 00384 //keep pulling out vertex of min wt from vt 00385 while(!vt.empty()){ 00386 Node *u=*(min_element(vt.begin(), vt.end(), compare_nodes())); 00387 DEBUG(std::cerr<<"popped wt"<<(u)->getWeight()<<"\n"; 00388 printNode(u)); 00389 00390 if(parent[u]!=NULL){ //so not root 00391 Edge edge(parent[u],u, ed_weight[u]); //assign edge in spanning tree 00392 st->addEdge(edge,ed_weight[u]); 00393 00394 DEBUG(std::cerr<<"added:\n"; 00395 printEdge(edge)); 00396 } 00397 00398 //vt.erase(u); 00399 00400 //remove u frm vt 00401 for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){ 00402 if(**VI==*u){ 00403 vt.erase(VI); 00404 break; 00405 } 00406 } 00407 00408 //assign wt(v) to all adjacent vertices v of u 00409 //only if v is in vt 00410 Graph::nodeList &nl = getNodeList(u); 00411 for(nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){ 00412 Node *v=NI->element; 00413 int weight=-NI->weight; 00414 //check if v is in vt 00415 bool contains=false; 00416 for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){ 00417 if(**VI==*v){ 00418 contains=true; 00419 break; 00420 } 00421 } 00422 DEBUG(std::cerr<<"wt:v->wt"<<weight<<":"<<v->getWeight()<<"\n"; 00423 printNode(v);std::cerr<<"node wt:"<<(*v).weight<<"\n"); 00424 00425 //so if v in in vt, change wt(v) to wt(u->v) 00426 //only if wt(u->v)<wt(v) 00427 if(contains && weight<v->getWeight()){ 00428 parent[v]=u; 00429 ed_weight[v]=weight; 00430 v->setWeight(weight); 00431 00432 DEBUG(std::cerr<<v->getWeight()<<":Set weight------\n"; 00433 printGraph(); 00434 printEdge(Edge(u,v,weight))); 00435 } 00436 } 00437 } 00438 return st; 00439 } 00440 00441 //print the graph (for debugging) 00442 void Graph::printGraph(){ 00443 vector<Node *> lt=getAllNodes(); 00444 std::cerr<<"Graph---------------------\n"; 00445 for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){ 00446 std::cerr<<((*LI)->getElement())->getName()<<"->"; 00447 Graph::nodeList &nl = getNodeList(*LI); 00448 for(Graph::nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){ 00449 std::cerr<<":"<<"("<<(NI->element->getElement()) 00450 ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")"; 00451 } 00452 std::cerr<<"--------\n"; 00453 } 00454 } 00455 00456 00457 //get a list of nodes in the graph 00458 //in r-topological sorted order 00459 //note that we assumed graph to be connected 00460 vector<Node *> Graph::reverseTopologicalSort(){ 00461 vector <Node *> toReturn; 00462 vector<Node *> lt=getAllNodes(); 00463 for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){ 00464 if((*LI)->getWeight()!=GREY && (*LI)->getWeight()!=BLACK) 00465 DFS_Visit(*LI, toReturn); 00466 } 00467 00468 return toReturn; 00469 } 00470 00471 //a private method for doing DFS traversal of graph 00472 //this is used in determining the reverse topological sort 00473 //of the graph 00474 void Graph::DFS_Visit(Node *nd, vector<Node *> &toReturn){ 00475 nd->setWeight(GREY); 00476 vector<Node *> lt=getSuccNodes(nd); 00477 for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){ 00478 if((*LI)->getWeight()!=GREY && (*LI)->getWeight()!=BLACK) 00479 DFS_Visit(*LI, toReturn); 00480 } 00481 toReturn.push_back(nd); 00482 } 00483 00484 //Ordinarily, the graph is directional 00485 //this converts the graph into an 00486 //undirectional graph 00487 //This is done by adding an edge 00488 //v->u for all existing edges u->v 00489 void Graph::makeUnDirectional(){ 00490 vector<Node* > allNodes=getAllNodes(); 00491 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 00492 ++NI) { 00493 nodeList &nl = getNodeList(*NI); 00494 for(nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE; ++NLI){ 00495 Edge ed(NLI->element, *NI, NLI->weight); 00496 if(!hasEdgeAndWt(ed)){ 00497 DEBUG(std::cerr<<"######doesn't hv\n"; 00498 printEdge(ed)); 00499 addEdgeForce(ed); 00500 } 00501 } 00502 } 00503 } 00504 00505 //reverse the sign of weights on edges 00506 //this way, max-spanning tree could be obtained 00507 //using min-spanning tree, and vice versa 00508 void Graph::reverseWts(){ 00509 vector<Node *> allNodes=getAllNodes(); 00510 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 00511 ++NI) { 00512 nodeList &node_list = getNodeList(*NI); 00513 for(nodeList::iterator NLI=nodes[*NI].begin(), NLE=nodes[*NI].end(); 00514 NLI!=NLE; ++NLI) 00515 NLI->weight=-NLI->weight; 00516 } 00517 } 00518 00519 00520 //getting the backedges in a graph 00521 //Its a variation of DFS to get the backedges in the graph 00522 //We get back edges by associating a time 00523 //and a color with each vertex. 00524 //The time of a vertex is the time when it was first visited 00525 //The color of a vertex is initially WHITE, 00526 //Changes to GREY when it is first visited, 00527 //and changes to BLACK when ALL its neighbors 00528 //have been visited 00529 //So we have a back edge when we meet a successor of 00530 //a node with smaller time, and GREY color 00531 void Graph::getBackEdges(vector<Edge > &be, std::map<Node *, int> &d){ 00532 std::map<Node *, Color > color; 00533 int time=0; 00534 00535 getBackEdgesVisit(getRoot(), be, color, d, time); 00536 } 00537 00538 //helper function to get back edges: it is called by 00539 //the "getBackEdges" function above 00540 void Graph::getBackEdgesVisit(Node *u, vector<Edge > &be, 00541 std::map<Node *, Color > &color, 00542 std::map<Node *, int > &d, int &time) { 00543 color[u]=GREY; 00544 time++; 00545 d[u]=time; 00546 00547 vector<graphListElement> &succ_list = getNodeList(u); 00548 00549 for(vector<graphListElement>::iterator vl=succ_list.begin(), 00550 ve=succ_list.end(); vl!=ve; ++vl){ 00551 Node *v=vl->element; 00552 if(color[v]!=GREY && color[v]!=BLACK){ 00553 getBackEdgesVisit(v, be, color, d, time); 00554 } 00555 00556 //now checking for d and f vals 00557 if(color[v]==GREY){ 00558 //so v is ancestor of u if time of u > time of v 00559 if(d[u] >= d[v]){ 00560 Edge *ed=new Edge(u, v,vl->weight, vl->randId); 00561 if (!(*u == *getExit() && *v == *getRoot())) 00562 be.push_back(*ed); // choose the forward edges 00563 } 00564 } 00565 } 00566 color[u]=BLACK;//done with visiting the node and its neighbors 00567 } 00568 00569 } // End llvm namespace