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 "llvm/BasicBlock.h"
20 //It forms the vertex for the graph
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; }
38 //Denotes an edge in the graph
47 inline Edge(Node *f,Node *s, int wt=0){
55 inline Edge(Node *f,Node *s, int wt, double rd){
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; }
70 inline int getWeight() { assert(!isNull()); return weight; }
71 inline void setWeight(int n) { assert(!isNull()); weight=n; }
73 inline void setFirst(Node *&f) { assert(!isNull()); first=f; }
74 inline void setSecond(Node *&s) { assert(!isNull()); second=s; }
77 inline bool isNull() const { return isnull;}
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())
84 return (*first<*(ed.getFirst()))||
85 (*first==*(ed.getFirst()) && *second<*(ed.getSecond()));
88 inline bool operator==(const Edge& ed) const{
89 return !(*this<ed) && !(ed<*this);
92 inline bool operator!=(const Edge& ed) const{return !(*this==ed);}
97 //This forms the "adjacency list element" of a
98 //vertex adjacency list in graph
99 struct graphListElement{
103 inline graphListElement(Node *n, int w, double rand){
112 struct less<Node *> : public binary_function<Node *, Node *,bool> {
113 bool operator()(Node *n1, Node *n2) const {
114 return n1->getElement() < n2->getElement();
118 struct less<Edge> : public binary_function<Edge,Edge,bool> {
119 bool operator()(Edge e1, Edge e2) const {
120 assert(!e1.isNull() && !e2.isNull());
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));
132 bool operator()(BasicBlock *BB1, BasicBlock *BB2) const{
133 std::string name1=BB1->getName();
134 std::string name2=BB2->getName();
140 bool operator()(graphListElement BB1, graphListElement BB2) const{
141 std::string name1=BB1.element->getElement()->getName();
142 std::string name2=BB2.element->getElement()->getName();
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));
163 //struct EdgeCompare2{
164 //bool operator()(Edge e1, Edge e2) const {
165 // assert(!e1.isNull() && !e2.isNull());
166 // return (e1.getRandId()<e2.getRandId());
171 //this is used to color vertices
180 //For path profiling,
181 //We assume that the graph is connected (which is true for
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
189 //graph uses adjacency list representation
192 //typedef std::map<Node*, std::list<graphListElement> > nodeMapTy;
193 typedef std::map<Node*, std::vector<graphListElement> > nodeMapTy;//chng
195 //the adjacency list of a vertex or node
198 //the start or root node
204 //a private method for doing DFS traversal of graph
205 //this is used in determining the reverse topological sort
207 void DFS_Visit(Node *nd, std::vector<Node *> &toReturn);
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
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,
226 typedef nodeMapTy::iterator elementIterator;
227 typedef nodeMapTy::const_iterator constElementIterator;
228 typedef std::vector<graphListElement > nodeList;//chng
229 //typedef std::vector<graphListElement > nodeList;
233 //empty constructor: then add edges and nodes later on
236 //constructor with root and exit node specified
237 Graph(std::vector<Node*> n,
238 std::vector<Edge> e, Node *rt, Node *lt);
241 void addNode(Node *nd);
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
248 void addEdge(Edge ed, int w);
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);
256 //set the weight of an edge
257 void setWeight(Edge ed);
260 //Note that it removes just one edge,
261 //the first edge that is encountered
262 void removeEdge(Edge ed);
264 //remove edge with given wt
265 void removeEdgeWithWt(Edge ed);
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);
273 //check whether graph has an edge, with a given wt
274 bool hasEdgeAndWt(Edge ed);
276 //get the list of successor nodes
277 std::vector<Node *> getSuccNodes(Node *nd);
279 //get the number of outgoing edges
280 int getNumberOfOutgoingEdges(Node *nd) const;
282 //get the list of predecessor nodes
283 std::vector<Node *> getPredNodes(Node *nd);
286 //to get the no of incoming edges
287 int getNumberOfIncomingEdges(Node *nd);
289 //get the list of all the vertices in graph
290 std::vector<Node *> getAllNodes() const;
291 std::vector<Node *> getAllNodes();
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();
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
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();
310 //print graph: for debugging
313 //get a vector of back edges in the graph
314 void getBackEdges(std::vector<Edge> &be, std::map<Node *, int> &d);
316 nodeList &sortNodeList(Node *par, nodeList &nl, std::vector<Edge> &be);
318 //Get the Maximal spanning tree (also a graph)
320 Graph* getMaxSpanningTree();
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);
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);
337 //get the root of the graph
338 inline Node *getRoot() {return strt; }
339 inline Node * const getRoot() const {return strt; }
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); }
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); }
352 //This class is used to generate
353 //"appropriate" code to be inserted
355 //The code to be inserted can be of six different types
357 //1: r=k (where k is some constant)
366 //"kind" of code is to be inserted
369 //inc is the increment: eg k, or 0
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
379 //incoming dummy edge, if any
382 //outgoing dummy edge, if any
394 inline void setCond(int n) {cond=n;}
397 inline int getCond() { return cond;}
400 inline void setInc(int n) {inc=n;}
403 inline int getInc() {return inc;}
405 //set CdIn (only used for backedges)
406 inline void setCdIn(getEdgeCode *gd){ cdIn=gd;}
408 //set CdOut (only used for backedges)
409 inline void setCdOut(getEdgeCode *gd){ cdOut=gd;}
411 //get the code to be inserted on the edge
412 //This is determined from cond (1-6)
413 void getCode(Instruction *a, Value *b, Function *M, BasicBlock *BB,
414 std::vector<Value *> &retVec);
418 //auxillary functions on graph
420 //print a given edge in the form BB1Label->BB2Label
421 void printEdge(Edge ed);
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, Value *countInst, std::vector<Edge> &be, std::vector<Edge> &stDummy, std::vector<Edge> &exDummy, int n, int MethNo, Value *threshold);
428 //print the graph (for debugging)
429 void printGraph(Graph &g);
432 //void printGraph(const Graph g);
433 //insert a basic block with appropriate code
435 void insertBB(Edge ed, getEdgeCode *edgeCode, Instruction *rInst, Value *countInst, int n, int Methno, Value *threshold);
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, Value *threshold);
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);
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);
460 void getBBtrace(std::vector<BasicBlock *> &vBB, int pathNo, Function *M);