1 //===-- ------------------------llvm/graph.h ---------------------*- C++ -*--=//
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
7 //===----------------------------------------------------------------------===//
12 #include "Support/StatisticReporter.h"
18 #include "llvm/BasicBlock.h"
26 //It forms the vertex for the graph
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; }
44 //Denotes an edge in the graph
53 inline Edge(Node *f,Node *s, int wt=0){
61 inline Edge(Node *f,Node *s, int wt, double rd){
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; }
76 inline int getWeight() { assert(!isNull()); return weight; }
77 inline void setWeight(int n) { assert(!isNull()); weight=n; }
79 inline void setFirst(Node *&f) { assert(!isNull()); first=f; }
80 inline void setSecond(Node *&s) { assert(!isNull()); second=s; }
83 inline bool isNull() const { return isnull;}
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())
90 return (*first<*(ed.getFirst()))||
91 (*first==*(ed.getFirst()) && *second<*(ed.getSecond()));
94 inline bool operator==(const Edge& ed) const{
95 return !(*this<ed) && !(ed<*this);
98 inline bool operator!=(const Edge& ed) const{return !(*this==ed);}
103 //This forms the "adjacency list element" of a
104 //vertex adjacency list in graph
105 struct graphListElement{
109 inline graphListElement(Node *n, int w, double rand){
118 struct less<Node *> : public binary_function<Node *, Node *,bool> {
119 bool operator()(Node *n1, Node *n2) const {
120 return n1->getElement() < n2->getElement();
124 struct less<Edge> : public binary_function<Edge,Edge,bool> {
125 bool operator()(Edge e1, Edge e2) const {
126 assert(!e1.isNull() && !e2.isNull());
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));
138 bool operator()(BasicBlock *BB1, BasicBlock *BB2) const{
139 std::string name1=BB1->getName();
140 std::string name2=BB2->getName();
146 bool operator()(graphListElement BB1, graphListElement BB2) const{
147 std::string name1=BB1.element->getElement()->getName();
148 std::string name2=BB2.element->getElement()->getName();
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));
169 //struct EdgeCompare2{
170 //bool operator()(Edge e1, Edge e2) const {
171 // assert(!e1.isNull() && !e2.isNull());
172 // return (e1.getRandId()<e2.getRandId());
177 //this is used to color vertices
186 //For path profiling,
187 //We assume that the graph is connected (which is true for
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
195 //graph uses adjacency list representation
198 //typedef std::map<Node*, std::list<graphListElement> > nodeMapTy;
199 typedef std::map<Node*, std::vector<graphListElement> > nodeMapTy;//chng
201 //the adjacency list of a vertex or node
204 //the start or root node
210 //a private method for doing DFS traversal of graph
211 //this is used in determining the reverse topological sort
213 void DFS_Visit(Node *nd, std::vector<Node *> &toReturn);
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
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,
232 typedef nodeMapTy::iterator elementIterator;
233 typedef nodeMapTy::const_iterator constElementIterator;
234 typedef std::vector<graphListElement > nodeList;//chng
235 //typedef std::vector<graphListElement > nodeList;
239 //empty constructor: then add edges and nodes later on
242 //constructor with root and exit node specified
243 Graph(std::vector<Node*> n,
244 std::vector<Edge> e, Node *rt, Node *lt);
247 void addNode(Node *nd);
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
254 void addEdge(Edge ed, int w);
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);
262 //set the weight of an edge
263 void setWeight(Edge ed);
266 //Note that it removes just one edge,
267 //the first edge that is encountered
268 void removeEdge(Edge ed);
270 //remove edge with given wt
271 void removeEdgeWithWt(Edge ed);
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);
279 //check whether graph has an edge, with a given wt
280 bool hasEdgeAndWt(Edge ed);
282 //get the list of successor nodes
283 std::vector<Node *> getSuccNodes(Node *nd);
285 //get the number of outgoing edges
286 int getNumberOfOutgoingEdges(Node *nd) const;
288 //get the list of predecessor nodes
289 std::vector<Node *> getPredNodes(Node *nd);
292 //to get the no of incoming edges
293 int getNumberOfIncomingEdges(Node *nd);
295 //get the list of all the vertices in graph
296 std::vector<Node *> getAllNodes() const;
297 std::vector<Node *> getAllNodes();
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();
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
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();
316 //print graph: for debugging
319 //get a vector of back edges in the graph
320 void getBackEdges(std::vector<Edge> &be, std::map<Node *, int> &d);
322 nodeList &sortNodeList(Node *par, nodeList &nl, std::vector<Edge> &be);
324 //Get the Maximal spanning tree (also a graph)
326 Graph* getMaxSpanningTree();
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);
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);
343 //get the root of the graph
344 inline Node *getRoot() {return strt; }
345 inline Node * const getRoot() const {return strt; }
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); }
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); }
358 //This class is used to generate
359 //"appropriate" code to be inserted
361 //The code to be inserted can be of six different types
363 //1: r=k (where k is some constant)
372 //"kind" of code is to be inserted
375 //inc is the increment: eg k, or 0
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
385 //incoming dummy edge, if any
388 //outgoing dummy edge, if any
400 inline void setCond(int n) {cond=n;}
403 inline int getCond() { return cond;}
406 inline void setInc(int n) {inc=n;}
409 inline int getInc() {return inc;}
411 //set CdIn (only used for backedges)
412 inline void setCdIn(getEdgeCode *gd){ cdIn=gd;}
414 //set CdOut (only used for backedges)
415 inline void setCdOut(getEdgeCode *gd){ cdOut=gd;}
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);
424 //auxillary functions on graph
426 //print a given edge in the form BB1Label->BB2Label
427 void printEdge(Edge ed);
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);
434 //print the graph (for debugging)
435 void printGraph(Graph &g);
438 //void printGraph(const Graph g);
439 //insert a basic block with appropriate code
441 void insertBB(Edge ed, getEdgeCode *edgeCode, Instruction *rInst, Instruction *countInst, int n, int Methno, Value *threshold);
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);
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);
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);
466 void getBBtrace(std::vector<BasicBlock *> &vBB, int pathNo, Function *M);