LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

Graph.cpp

Go to the documentation of this file.
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