lib/Transforms/Instrumentation/ProfilePaths/Graph.h

   1 //===-- ------------------------llvm/graph.h ---------------------*- C++ -*--=//
   2 //
   3 //Header file for Graph: This Graph is used by
   4 //PathProfiles class, and is used
   5 //for detecting proper points in cfg for code insertion
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef LLVM_GRAPH_H
  10 #define LLVM_GRAPH_H
  11
  12 #include "llvm/BasicBlock.h"
  13 #include <map>
  14 #include <cstdlib>
  15
  16 class Module;
  17 class Function;
  18
  19 //Class Node
  20 //It forms the vertex for the graph
  21 class Node{
  22 public:
  23   BasicBlock* element;
  24   int weight;
  25 public:
  26   inline Node(BasicBlock* x) { element=x; weight=0; }
  27   inline BasicBlock* &getElement() { return element; }
  28   inline BasicBlock* const &getElement() const { return element; }
  29   inline int getWeight() { return weight; }
  30   inline void setElement(BasicBlock* e) { element=e; }
  31   inline void setWeight(int w) { weight=w;}
  32   inline bool operator<(Node& nd) const { return element<nd.element; }
  33   inline bool operator==(Node& nd) const { return element==nd.element; }
  34 };
  35
  36
  37 //Class Edge
  38 //Denotes an edge in the graph
  39 class Edge{
  40 private:
  41   Node *first;
  42   Node *second;
  43   bool isnull;
  44   int weight;
  45   double randId;
  46 public:
  47   inline Edge(Node *f,Node *s, int wt=0){
  48     first=f;
  49     second=s;
  50     weight=wt;
  51     randId=rand();
  52     isnull=false;
  53   }
  54
  55   inline Edge(Node *f,Node *s, int wt, double rd){
  56     first=f;
  57     second=s;
  58     weight=wt;
  59     randId=rd;
  60     isnull=false;
  61   }
  62
  63   inline Edge() { isnull = true; }
  64   inline double getRandId(){ return randId; }
  65   inline Node* getFirst() { assert(!isNull()); return first; }
  66   inline Node* const getFirst() const { assert(!isNull()); return first; }
  67   inline Node* getSecond() { assert(!isNull()); return second; }
  68   inline Node* const getSecond() const { assert(!isNull()); return second; }
  69
  70   inline int getWeight() { assert(!isNull());  return weight; }
  71   inline void setWeight(int n) { assert(!isNull()); weight=n; }
  72
  73   inline void setFirst(Node *&f) { assert(!isNull());  first=f; }
  74   inline void setSecond(Node *&s) { assert(!isNull()); second=s; }
  75
  76
  77   inline bool isNull() const { return isnull;}
  78
  79   inline bool operator<(const Edge& ed) const{
  80     // Can't be the same if one is null and the other isn't
  81     if (isNull() != ed.isNull())
  82       return true;
  83
  84     return (*first<*(ed.getFirst()))||
  85       (*first==*(ed.getFirst()) && *second<*(ed.getSecond()));
  86   }
  87
  88   inline bool operator==(const Edge& ed) const{
  89     return !(*this<ed) && !(ed<*this);
  90   }
  91
  92   inline bool operator!=(const Edge& ed) const{return !(*this==ed);}
  93 };
  94
  95
  96 //graphListElement
  97 //This forms the "adjacency list element" of a
  98 //vertex adjacency list in graph
  99 struct graphListElement{
 100   Node *element;
 101   int weight;
 102   double randId;
 103   inline graphListElement(Node *n, int w, double rand){
 104     element=n;
 105     weight=w;
 106     randId=rand;
 107   }
 108 };
 109
 110
 111 namespace std {
 112   struct less<Node *> : public binary_function<Node *, Node *,bool> {
 113     bool operator()(Node *n1, Node *n2) const {
 114       return n1->getElement() < n2->getElement();
 115     }
 116   };
 117
 118   struct less<Edge> : public binary_function<Edge,Edge,bool> {
 119     bool operator()(Edge e1, Edge e2) const {
 120       assert(!e1.isNull() && !e2.isNull());
 121
 122       Node *x1=e1.getFirst();
 123       Node *x2=e1.getSecond();
 124       Node *y1=e2.getFirst();
 125       Node *y2=e2.getSecond();
 126       return (*x1<*y1 ||(*x1==*y1 && *x2<*y2));
 127     }
 128   };
 129 }
 130
 131 struct BBSort{
 132   bool operator()(BasicBlock *BB1, BasicBlock *BB2) const{
 133     std::string name1=BB1->getName();
 134     std::string name2=BB2->getName();
 135     return name1<name2;
 136   }
 137 };
 138
 139 struct NodeListSort{
 140   bool operator()(graphListElement BB1, graphListElement BB2) const{
 141     std::string name1=BB1.element->getElement()->getName();
 142     std::string name2=BB2.element->getElement()->getName();
 143     return name1<name2;
 144   }
 145 };
 146
 147 struct EdgeCompare2{
 148   bool operator()(Edge e1, Edge e2) const {
 149     assert(!e1.isNull() && !e2.isNull());
 150     Node *x1=e1.getFirst();
 151     Node *x2=e1.getSecond();
 152     Node *y1=e2.getFirst();
 153     Node *y2=e2.getSecond();
 154     int w1=e1.getWeight();
 155     int w2=e2.getWeight();
 156     double r1 = e1.getRandId();
 157     double r2 = e2.getRandId();
 158     //return (*x1<*y1 || (*x1==*y1 && *x2<*y2) || (*x1==*y1 && *x2==*y2 && w1<w2));
 159     return (*x1<*y1 || (*x1==*y1 && *x2<*y2) || (*x1==*y1 && *x2==*y2 && w1<w2) || (*x1==*y1 && *x2==*y2 && w1==w2 && r1<r2));
 160   }
 161 };
 162
 163 //struct EdgeCompare2{
 164 //bool operator()(Edge e1, Edge e2) const {
 165 //  assert(!e1.isNull() && !e2.isNull());
 166 //  return (e1.getRandId()<e2.getRandId());
 167 //}
 168 //};
 169
 170
 171 //this is used to color vertices
 172 //during DFS
 173 enum Color{
 174   WHITE,
 175   GREY,
 176   BLACK
 177 };
 178
 179
 180 //For path profiling,
 181 //We assume that the graph is connected (which is true for
 182 //any method CFG)
 183 //We also assume that the graph has single entry and single exit
 184 //(For this, we make a pass over the graph that ensures this)
 185 //The graph is a construction over any existing graph of BBs
 186 //Its a construction "over" existing cfg: with
 187 //additional features like edges and weights to edges
 188
 189 //graph uses adjacency list representation
 190 class Graph{
 191 public:
 192   //typedef std::map<Node*, std::list<graphListElement> > nodeMapTy;
 193   typedef std::map<Node*, std::vector<graphListElement> > nodeMapTy;//chng
 194 private:
 195   //the adjacency list of a vertex or node
 196   nodeMapTy nodes;
 197
 198   //the start or root node
 199   Node *strt;
 200
 201   //the exit node
 202   Node *ext;
 203
 204   //a private method for doing DFS traversal of graph
 205   //this is used in determining the reverse topological sort
 206   //of the graph
 207   void DFS_Visit(Node *nd, std::vector<Node *> &toReturn);
 208
 209   //Its a variation of DFS to get the backedges in the graph
 210   //We get back edges by associating a time
 211   //and a color with each vertex.
 212   //The time of a vertex is the time when it was first visited
 213   //The color of a vertex is initially WHITE,
 214   //Changes to GREY when it is first visited,
 215   //and changes to BLACK when ALL its neighbors
 216   //have been visited
 217   //So we have a back edge when we meet a successor of
 218   //a node with smaller time, and GREY color
 219   void getBackEdgesVisit(Node *u,
 220                          std::vector<Edge > &be,
 221                          std::map<Node *, Color> &clr,
 222                          std::map<Node *, int> &d,
 223                          int &time);
 224
 225 public:
 226   typedef nodeMapTy::iterator elementIterator;
 227   typedef nodeMapTy::const_iterator constElementIterator;
 228   typedef std::vector<graphListElement > nodeList;//chng
 229   //typedef std::vector<graphListElement > nodeList;
 230
 231   //graph constructors
 232
 233   //empty constructor: then add edges and nodes later on
 234   Graph() {}
 235
 236   //constructor with root and exit node specified
 237   Graph(std::vector<Node*> n,
 238         std::vector<Edge> e, Node *rt, Node *lt);
 239
 240   //add a node
 241   void addNode(Node *nd);
 242
 243   //add an edge
 244   //this adds an edge ONLY when
 245   //the edge to be added doesn not already exist
 246   //we "equate" two edges here only with their
 247   //end points
 248   void addEdge(Edge ed, int w);
 249
 250   //add an edge EVEN IF such an edge already exists
 251   //this may make a multi-graph
 252   //which does happen when we add dummy edges
 253   //to the graph, for compensating for back-edges
 254   void addEdgeForce(Edge ed);
 255
 256   //set the weight of an edge
 257   void setWeight(Edge ed);
 258
 259   //remove an edge
 260   //Note that it removes just one edge,
 261   //the first edge that is encountered
 262   void removeEdge(Edge ed);
 263
 264   //remove edge with given wt
 265   void removeEdgeWithWt(Edge ed);
 266
 267   //check whether graph has an edge
 268   //having an edge simply means that there is an edge in the graph
 269   //which has same endpoints as the given edge
 270   //it may possibly have different weight though
 271   bool hasEdge(Edge ed);
 272
 273   //check whether graph has an edge, with a given wt
 274   bool hasEdgeAndWt(Edge ed);
 275
 276   //get the list of successor nodes
 277   std::vector<Node *> getSuccNodes(Node *nd);
 278
 279   //get the number of outgoing edges
 280   int getNumberOfOutgoingEdges(Node *nd) const;
 281
 282   //get the list of predecessor nodes
 283   std::vector<Node *> getPredNodes(Node *nd);
 284
 285
 286   //to get the no of incoming edges
 287   int getNumberOfIncomingEdges(Node *nd);
 288
 289   //get the list of all the vertices in graph
 290   std::vector<Node *> getAllNodes() const;
 291   std::vector<Node *> getAllNodes();
 292
 293   //get a list of nodes in the graph
 294   //in r-topological sorted order
 295   //note that we assumed graph to be connected
 296   std::vector<Node *> reverseTopologicalSort();
 297
 298   //reverse the sign of weights on edges
 299   //this way, max-spanning tree could be obtained
 300   //usin min-spanning tree, and vice versa
 301   void reverseWts();
 302
 303   //Ordinarily, the graph is directional
 304   //this converts the graph into an
 305   //undirectional graph
 306   //This is done by adding an edge
 307   //v->u for all existing edges u->v
 308   void makeUnDirectional();
 309
 310   //print graph: for debugging
 311   void printGraph();
 312
 313   //get a vector of back edges in the graph
 314   void getBackEdges(std::vector<Edge> &be, std::map<Node *, int> &d);
 315
 316   nodeList &sortNodeList(Node *par, nodeList &nl, std::vector<Edge> &be);
 317
 318   //Get the Maximal spanning tree (also a graph)
 319   //of the graph
 320   Graph* getMaxSpanningTree();
 321
 322   //get the nodeList adjacent to a node
 323   //a nodeList element contains a node, and the weight
 324   //corresponding to the edge for that element
 325   inline nodeList &getNodeList(Node *nd) {
 326     elementIterator nli = nodes.find(nd);
 327     assert(nli != nodes.end() && "Node must be in nodes map");
 328     return nodes[nd];//sortNodeList(nd, nli->second);
 329   }
 330
 331   nodeList &getSortedNodeList(Node *nd, std::vector<Edge> &be) {
 332     elementIterator nli = nodes.find(nd);
 333     assert(nli != nodes.end() && "Node must be in nodes map");
 334     return sortNodeList(nd, nodes[nd], be);
 335   }
 336
 337   //get the root of the graph
 338   inline Node *getRoot()                {return strt; }
 339   inline Node * const getRoot() const   {return strt; }
 340
 341   //get exit: we assumed there IS a unique exit :)
 342   inline Node *getExit()                {return ext; }
 343   inline Node * const getExit() const   {return ext; }
 344   //Check if a given node is the root
 345   inline bool isRoot(Node *n) const     {return (*n==*strt); }
 346
 347   //check if a given node is leaf node
 348   //here we hv only 1 leaf: which is the exit node
 349   inline bool isLeaf(Node *n)    const  {return (*n==*ext);  }
 350 };
 351
 352 //This class is used to generate
 353 //"appropriate" code to be inserted
 354 //along an edge
 355 //The code to be inserted can be of six different types
 356 //as given below
 357 //1: r=k (where k is some constant)
 358 //2: r=0
 359 //3: r+=k
 360 //4: count[k]++
 361 //5: Count[r+k]++
 362 //6: Count[r]++
 363 class getEdgeCode{
 364  private:
 365   //cond implies which
 366   //"kind" of code is to be inserted
 367   //(from 1-6 above)
 368   int cond;
 369   //inc is the increment: eg k, or 0
 370   int inc;
 371
 372   //A backedge must carry the code
 373   //of both incoming "dummy" edge
 374   //and outgoing "dummy" edge
 375   //If a->b is a backedge
 376   //then incoming dummy edge is root->b
 377   //and outgoing dummy edge is a->exit
 378
 379   //incoming dummy edge, if any
 380   getEdgeCode *cdIn;
 381
 382   //outgoing dummy edge, if any
 383   getEdgeCode *cdOut;
 384
 385 public:
 386   getEdgeCode(){
 387     cdIn=NULL;
 388     cdOut=NULL;
 389     inc=0;
 390     cond=0;
 391   }
 392
 393   //set condition: 1-6
 394   inline void setCond(int n) {cond=n;}
 395
 396   //get the condition
 397   inline int getCond() { return cond;}
 398
 399   //set increment
 400   inline void setInc(int n) {inc=n;}
 401
 402   //get increment
 403   inline int getInc() {return inc;}
 404
 405   //set CdIn (only used for backedges)
 406   inline void setCdIn(getEdgeCode *gd){ cdIn=gd;}
 407
 408   //set CdOut (only used for backedges)
 409   inline void setCdOut(getEdgeCode *gd){ cdOut=gd;}
 410
 411   //get the code to be inserted on the edge
 412   //This is determined from cond (1-6)
 413   void getCode(Instruction *a, Instruction *b, Function *M, BasicBlock *BB,
 414                std::vector<Value *> &retVec);
 415 };
 416
 417
 418 //auxillary functions on graph
 419
 420 //print a given edge in the form BB1Label->BB2Label
 421 void printEdge(Edge ed);
 422
 423 //Do graph processing: to determine minimal edge increments,
 424 //appropriate code insertions etc and insert the code at
 425 //appropriate locations
 426 void processGraph(Graph &g, Instruction *rInst, Instruction *countInst, std::vector<Edge> &be, std::vector<Edge> &stDummy, std::vector<Edge> &exDummy, int n, int MethNo, Value *threshold);
 427
 428 //print the graph (for debugging)
 429 void printGraph(Graph &g);
 430
 431
 432 //void printGraph(const Graph g);
 433 //insert a basic block with appropriate code
 434 //along a given edge
 435 void insertBB(Edge ed, getEdgeCode *edgeCode, Instruction *rInst, Instruction *countInst, int n, int Methno, Value *threshold);
 436
 437 //Insert the initialization code in the top BB
 438 //this includes initializing r, and count
 439 //r is like an accumulator, that
 440 //keeps on adding increments as we traverse along a path
 441 //and at the end of the path, r contains the path
 442 //number of that path
 443 //Count is an array, where Count[k] represents
 444 //the number of executions of path k
 445 void insertInTopBB(BasicBlock *front, int k, Instruction *rVar, Instruction *countVar, Value *threshold);
 446
 447 //Add dummy edges corresponding to the back edges
 448 //If a->b is a backedge
 449 //then incoming dummy edge is root->b
 450 //and outgoing dummy edge is a->exit
 451 void addDummyEdges(std::vector<Edge> &stDummy, std::vector<Edge> &exDummy, Graph &g, std::vector<Edge> &be);
 452
 453 //Assign a value to all the edges in the graph
 454 //such that if we traverse along any path from root to exit, and
 455 //add up the edge values, we get a path number that uniquely
 456 //refers to the path we travelled
 457 int valueAssignmentToEdges(Graph& g, std::map<Node *, int> nodePriority,
 458                            std::vector<Edge> &be);
 459
 460 void getBBtrace(std::vector<BasicBlock *> &vBB, int pathNo, Function *M);
 461 #endif
 462
 463