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