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