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