LLVM API Documentation
00001 //===-- Graph.h -------------------------------------------------*- C++ -*-===// 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 // Header file for Graph: This Graph is used by PathProfiles class, and is used 00011 // for detecting proper points in cfg for code insertion 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #ifndef LLVM_GRAPH_H 00016 #define LLVM_GRAPH_H 00017 00018 #include "llvm/BasicBlock.h" 00019 #include <map> 00020 #include <cstdlib> 00021 00022 namespace llvm { 00023 00024 class Module; 00025 class Function; 00026 00027 //Class Node 00028 //It forms the vertex for the graph 00029 class Node{ 00030 public: 00031 BasicBlock* element; 00032 int weight; 00033 public: 00034 inline Node(BasicBlock* x) { element=x; weight=0; } 00035 inline BasicBlock* &getElement() { return element; } 00036 inline BasicBlock* const &getElement() const { return element; } 00037 inline int getWeight() { return weight; } 00038 inline void setElement(BasicBlock* e) { element=e; } 00039 inline void setWeight(int w) { weight=w;} 00040 inline bool operator<(Node& nd) const { return element<nd.element; } 00041 inline bool operator==(Node& nd) const { return element==nd.element; } 00042 }; 00043 00044 //Class Edge 00045 //Denotes an edge in the graph 00046 class Edge{ 00047 private: 00048 Node *first; 00049 Node *second; 00050 bool isnull; 00051 int weight; 00052 double randId; 00053 public: 00054 inline Edge(Node *f,Node *s, int wt=0){ 00055 first=f; 00056 second=s; 00057 weight=wt; 00058 randId=rand(); 00059 isnull=false; 00060 } 00061 00062 inline Edge(Node *f,Node *s, int wt, double rd){ 00063 first=f; 00064 second=s; 00065 weight=wt; 00066 randId=rd; 00067 isnull=false; 00068 } 00069 00070 inline Edge() { isnull = true; } 00071 inline double getRandId(){ return randId; } 00072 inline Node* getFirst() { assert(!isNull()); return first; } 00073 inline Node* const getFirst() const { assert(!isNull()); return first; } 00074 inline Node* getSecond() { assert(!isNull()); return second; } 00075 inline Node* const getSecond() const { assert(!isNull()); return second; } 00076 00077 inline int getWeight() { assert(!isNull()); return weight; } 00078 inline void setWeight(int n) { assert(!isNull()); weight=n; } 00079 00080 inline void setFirst(Node *&f) { assert(!isNull()); first=f; } 00081 inline void setSecond(Node *&s) { assert(!isNull()); second=s; } 00082 00083 00084 inline bool isNull() const { return isnull;} 00085 00086 inline bool operator<(const Edge& ed) const{ 00087 // Can't be the same if one is null and the other isn't 00088 if (isNull() != ed.isNull()) 00089 return true; 00090 00091 return (*first<*(ed.getFirst()))|| 00092 (*first==*(ed.getFirst()) && *second<*(ed.getSecond())); 00093 } 00094 00095 inline bool operator==(const Edge& ed) const{ 00096 return !(*this<ed) && !(ed<*this); 00097 } 00098 00099 inline bool operator!=(const Edge& ed) const{return !(*this==ed);} 00100 }; 00101 00102 00103 //graphListElement 00104 //This forms the "adjacency list element" of a 00105 //vertex adjacency list in graph 00106 struct graphListElement{ 00107 Node *element; 00108 int weight; 00109 double randId; 00110 inline graphListElement(Node *n, int w, double rand){ 00111 element=n; 00112 weight=w; 00113 randId=rand; 00114 } 00115 }; 00116 00117 } // End llvm namespace 00118 00119 00120 namespace std { 00121 00122 using namespace llvm; 00123 00124 template<> 00125 struct less<Node *> : public binary_function<Node *, Node *,bool> { 00126 bool operator()(Node *n1, Node *n2) const { 00127 return n1->getElement() < n2->getElement(); 00128 } 00129 }; 00130 00131 template<> 00132 struct less<Edge> : public binary_function<Edge,Edge,bool> { 00133 bool operator()(Edge e1, Edge e2) const { 00134 assert(!e1.isNull() && !e2.isNull()); 00135 00136 Node *x1=e1.getFirst(); 00137 Node *x2=e1.getSecond(); 00138 Node *y1=e2.getFirst(); 00139 Node *y2=e2.getSecond(); 00140 return (*x1<*y1 ||(*x1==*y1 && *x2<*y2)); 00141 } 00142 }; 00143 } 00144 00145 namespace llvm { 00146 00147 struct BBSort{ 00148 bool operator()(BasicBlock *BB1, BasicBlock *BB2) const{ 00149 std::string name1=BB1->getName(); 00150 std::string name2=BB2->getName(); 00151 return name1<name2; 00152 } 00153 }; 00154 00155 struct NodeListSort{ 00156 bool operator()(graphListElement BB1, graphListElement BB2) const{ 00157 std::string name1=BB1.element->getElement()->getName(); 00158 std::string name2=BB2.element->getElement()->getName(); 00159 return name1<name2; 00160 } 00161 }; 00162 00163 struct EdgeCompare2{ 00164 bool operator()(Edge e1, Edge e2) const { 00165 assert(!e1.isNull() && !e2.isNull()); 00166 Node *x1=e1.getFirst(); 00167 Node *x2=e1.getSecond(); 00168 Node *y1=e2.getFirst(); 00169 Node *y2=e2.getSecond(); 00170 int w1=e1.getWeight(); 00171 int w2=e2.getWeight(); 00172 double r1 = e1.getRandId(); 00173 double r2 = e2.getRandId(); 00174 //return (*x1<*y1 || (*x1==*y1 && *x2<*y2) || (*x1==*y1 && *x2==*y2 && w1<w2)); 00175 return (*x1<*y1 || (*x1==*y1 && *x2<*y2) || (*x1==*y1 && *x2==*y2 && w1<w2) || (*x1==*y1 && *x2==*y2 && w1==w2 && r1<r2)); 00176 } 00177 }; 00178 00179 //struct EdgeCompare2{ 00180 //bool operator()(Edge e1, Edge e2) const { 00181 // assert(!e1.isNull() && !e2.isNull()); 00182 // return (e1.getRandId()<e2.getRandId()); 00183 //} 00184 //}; 00185 00186 00187 //this is used to color vertices 00188 //during DFS 00189 enum Color{ 00190 WHITE, 00191 GREY, 00192 BLACK 00193 }; 00194 00195 00196 //For path profiling, 00197 //We assume that the graph is connected (which is true for 00198 //any method CFG) 00199 //We also assume that the graph has single entry and single exit 00200 //(For this, we make a pass over the graph that ensures this) 00201 //The graph is a construction over any existing graph of BBs 00202 //Its a construction "over" existing cfg: with 00203 //additional features like edges and weights to edges 00204 00205 //graph uses adjacency list representation 00206 class Graph{ 00207 public: 00208 //typedef std::map<Node*, std::list<graphListElement> > nodeMapTy; 00209 typedef std::map<Node*, std::vector<graphListElement> > nodeMapTy;//chng 00210 private: 00211 //the adjacency list of a vertex or node 00212 nodeMapTy nodes; 00213 00214 //the start or root node 00215 Node *strt; 00216 00217 //the exit node 00218 Node *ext; 00219 00220 //a private method for doing DFS traversal of graph 00221 //this is used in determining the reverse topological sort 00222 //of the graph 00223 void DFS_Visit(Node *nd, std::vector<Node *> &toReturn); 00224 00225 //Its a variation of DFS to get the backedges in the graph 00226 //We get back edges by associating a time 00227 //and a color with each vertex. 00228 //The time of a vertex is the time when it was first visited 00229 //The color of a vertex is initially WHITE, 00230 //Changes to GREY when it is first visited, 00231 //and changes to BLACK when ALL its neighbors 00232 //have been visited 00233 //So we have a back edge when we meet a successor of 00234 //a node with smaller time, and GREY color 00235 void getBackEdgesVisit(Node *u, 00236 std::vector<Edge > &be, 00237 std::map<Node *, Color> &clr, 00238 std::map<Node *, int> &d, 00239 int &time); 00240 00241 public: 00242 typedef nodeMapTy::iterator elementIterator; 00243 typedef nodeMapTy::const_iterator constElementIterator; 00244 typedef std::vector<graphListElement > nodeList;//chng 00245 //typedef std::vector<graphListElement > nodeList; 00246 00247 //graph constructors 00248 00249 //empty constructor: then add edges and nodes later on 00250 Graph() {} 00251 00252 //constructor with root and exit node specified 00253 Graph(std::vector<Node*> n, 00254 std::vector<Edge> e, Node *rt, Node *lt); 00255 00256 //add a node 00257 void addNode(Node *nd); 00258 00259 //add an edge 00260 //this adds an edge ONLY when 00261 //the edge to be added doesn not already exist 00262 //we "equate" two edges here only with their 00263 //end points 00264 void addEdge(Edge ed, int w); 00265 00266 //add an edge EVEN IF such an edge already exists 00267 //this may make a multi-graph 00268 //which does happen when we add dummy edges 00269 //to the graph, for compensating for back-edges 00270 void addEdgeForce(Edge ed); 00271 00272 //set the weight of an edge 00273 void setWeight(Edge ed); 00274 00275 //remove an edge 00276 //Note that it removes just one edge, 00277 //the first edge that is encountered 00278 void removeEdge(Edge ed); 00279 00280 //remove edge with given wt 00281 void removeEdgeWithWt(Edge ed); 00282 00283 //check whether graph has an edge 00284 //having an edge simply means that there is an edge in the graph 00285 //which has same endpoints as the given edge 00286 //it may possibly have different weight though 00287 bool hasEdge(Edge ed); 00288 00289 //check whether graph has an edge, with a given wt 00290 bool hasEdgeAndWt(Edge ed); 00291 00292 //get the list of successor nodes 00293 std::vector<Node *> getSuccNodes(Node *nd); 00294 00295 //get the number of outgoing edges 00296 int getNumberOfOutgoingEdges(Node *nd) const; 00297 00298 //get the list of predecessor nodes 00299 std::vector<Node *> getPredNodes(Node *nd); 00300 00301 00302 //to get the no of incoming edges 00303 int getNumberOfIncomingEdges(Node *nd); 00304 00305 //get the list of all the vertices in graph 00306 std::vector<Node *> getAllNodes() const; 00307 std::vector<Node *> getAllNodes(); 00308 00309 //get a list of nodes in the graph 00310 //in r-topological sorted order 00311 //note that we assumed graph to be connected 00312 std::vector<Node *> reverseTopologicalSort(); 00313 00314 //reverse the sign of weights on edges 00315 //this way, max-spanning tree could be obtained 00316 //usin min-spanning tree, and vice versa 00317 void reverseWts(); 00318 00319 //Ordinarily, the graph is directional 00320 //this converts the graph into an 00321 //undirectional graph 00322 //This is done by adding an edge 00323 //v->u for all existing edges u->v 00324 void makeUnDirectional(); 00325 00326 //print graph: for debugging 00327 void printGraph(); 00328 00329 //get a vector of back edges in the graph 00330 void getBackEdges(std::vector<Edge> &be, std::map<Node *, int> &d); 00331 00332 nodeList &sortNodeList(Node *par, nodeList &nl, std::vector<Edge> &be); 00333 00334 //Get the Maximal spanning tree (also a graph) 00335 //of the graph 00336 Graph* getMaxSpanningTree(); 00337 00338 //get the nodeList adjacent to a node 00339 //a nodeList element contains a node, and the weight 00340 //corresponding to the edge for that element 00341 inline nodeList &getNodeList(Node *nd) { 00342 elementIterator nli = nodes.find(nd); 00343 assert(nli != nodes.end() && "Node must be in nodes map"); 00344 return nodes[nd];//sortNodeList(nd, nli->second); 00345 } 00346 00347 nodeList &getSortedNodeList(Node *nd, std::vector<Edge> &be) { 00348 elementIterator nli = nodes.find(nd); 00349 assert(nli != nodes.end() && "Node must be in nodes map"); 00350 return sortNodeList(nd, nodes[nd], be); 00351 } 00352 00353 //get the root of the graph 00354 inline Node *getRoot() {return strt; } 00355 inline Node * const getRoot() const {return strt; } 00356 00357 //get exit: we assumed there IS a unique exit :) 00358 inline Node *getExit() {return ext; } 00359 inline Node * const getExit() const {return ext; } 00360 //Check if a given node is the root 00361 inline bool isRoot(Node *n) const {return (*n==*strt); } 00362 00363 //check if a given node is leaf node 00364 //here we hv only 1 leaf: which is the exit node 00365 inline bool isLeaf(Node *n) const {return (*n==*ext); } 00366 }; 00367 00368 //This class is used to generate 00369 //"appropriate" code to be inserted 00370 //along an edge 00371 //The code to be inserted can be of six different types 00372 //as given below 00373 //1: r=k (where k is some constant) 00374 //2: r=0 00375 //3: r+=k 00376 //4: count[k]++ 00377 //5: Count[r+k]++ 00378 //6: Count[r]++ 00379 class getEdgeCode{ 00380 private: 00381 //cond implies which 00382 //"kind" of code is to be inserted 00383 //(from 1-6 above) 00384 int cond; 00385 //inc is the increment: eg k, or 0 00386 int inc; 00387 00388 //A backedge must carry the code 00389 //of both incoming "dummy" edge 00390 //and outgoing "dummy" edge 00391 //If a->b is a backedge 00392 //then incoming dummy edge is root->b 00393 //and outgoing dummy edge is a->exit 00394 00395 //incoming dummy edge, if any 00396 getEdgeCode *cdIn; 00397 00398 //outgoing dummy edge, if any 00399 getEdgeCode *cdOut; 00400 00401 public: 00402 getEdgeCode(){ 00403 cdIn=NULL; 00404 cdOut=NULL; 00405 inc=0; 00406 cond=0; 00407 } 00408 00409 //set condition: 1-6 00410 inline void setCond(int n) {cond=n;} 00411 00412 //get the condition 00413 inline int getCond() { return cond;} 00414 00415 //set increment 00416 inline void setInc(int n) {inc=n;} 00417 00418 //get increment 00419 inline int getInc() {return inc;} 00420 00421 //set CdIn (only used for backedges) 00422 inline void setCdIn(getEdgeCode *gd){ cdIn=gd;} 00423 00424 //set CdOut (only used for backedges) 00425 inline void setCdOut(getEdgeCode *gd){ cdOut=gd;} 00426 00427 //get the code to be inserted on the edge 00428 //This is determined from cond (1-6) 00429 void getCode(Instruction *a, Value *b, Function *M, BasicBlock *BB, 00430 std::vector<Value *> &retVec); 00431 }; 00432 00433 00434 //auxillary functions on graph 00435 00436 //print a given edge in the form BB1Label->BB2Label 00437 void printEdge(Edge ed); 00438 00439 //Do graph processing: to determine minimal edge increments, 00440 //appropriate code insertions etc and insert the code at 00441 //appropriate locations 00442 void processGraph(Graph &g, Instruction *rInst, Value *countInst, std::vector<Edge> &be, std::vector<Edge> &stDummy, std::vector<Edge> &exDummy, int n, int MethNo, Value *threshold); 00443 00444 //print the graph (for debugging) 00445 void printGraph(Graph &g); 00446 00447 00448 //void printGraph(const Graph g); 00449 //insert a basic block with appropriate code 00450 //along a given edge 00451 void insertBB(Edge ed, getEdgeCode *edgeCode, Instruction *rInst, Value *countInst, int n, int Methno, Value *threshold); 00452 00453 //Insert the initialization code in the top BB 00454 //this includes initializing r, and count 00455 //r is like an accumulator, that 00456 //keeps on adding increments as we traverse along a path 00457 //and at the end of the path, r contains the path 00458 //number of that path 00459 //Count is an array, where Count[k] represents 00460 //the number of executions of path k 00461 void insertInTopBB(BasicBlock *front, int k, Instruction *rVar, Value *threshold); 00462 00463 //Add dummy edges corresponding to the back edges 00464 //If a->b is a backedge 00465 //then incoming dummy edge is root->b 00466 //and outgoing dummy edge is a->exit 00467 void addDummyEdges(std::vector<Edge> &stDummy, std::vector<Edge> &exDummy, Graph &g, std::vector<Edge> &be); 00468 00469 //Assign a value to all the edges in the graph 00470 //such that if we traverse along any path from root to exit, and 00471 //add up the edge values, we get a path number that uniquely 00472 //refers to the path we travelled 00473 int valueAssignmentToEdges(Graph& g, std::map<Node *, int> nodePriority, 00474 std::vector<Edge> &be); 00475 00476 void getBBtrace(std::vector<BasicBlock *> &vBB, int pathNo, Function *M); 00477 00478 } // End llvm namespace 00479 00480 #endif