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.h

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