#ifndef LLVM_GRAPH_H
#define LLVM_GRAPH_H
-#include "Support/StatisticReporter.h"
-
+#include "llvm/BasicBlock.h"
#include <map>
-//#include <list>
-//#include <set>
-#include <vector>
#include <cstdlib>
-#include "llvm/BasicBlock.h"
-
-class BasicBlock;
-//class Method;
class Module;
-//=======
class Function;
-//>>>>>>> 1.4
-class Instruction;
//Class Node
//It forms the vertex for the graph
inline bool operator<(Node& nd) const { return element<nd.element; }
inline bool operator==(Node& nd) const { return element==nd.element; }
};
-////////////////////////
+
//Class Edge
//Denotes an edge in the graph
inline bool operator!=(const Edge& ed) const{return !(*this==ed);}
};
-////////////////////////
+
//graphListElement
//This forms the "adjacency list element" of a
randId=rand;
}
};
-/////////////////////////
+
namespace std {
struct less<Node *> : public binary_function<Node *, Node *,bool> {
return name1<name2;
}
};
-struct EdgeCompare{
+
+struct EdgeCompare2{
bool operator()(Edge e1, Edge e2) const {
assert(!e1.isNull() && !e2.isNull());
Node *x1=e1.getFirst();
Node *y2=e2.getSecond();
int w1=e1.getWeight();
int w2=e2.getWeight();
- return (*x1<*y1 || (*x1==*y1 && *x2<*y2) || (*x1==*y1 && *x2==*y2 && w1<w2));
+ double r1 = e1.getRandId();
+ double r2 = e2.getRandId();
+ //return (*x1<*y1 || (*x1==*y1 && *x2<*y2) || (*x1==*y1 && *x2==*y2 && w1<w2));
+ return (*x1<*y1 || (*x1==*y1 && *x2<*y2) || (*x1==*y1 && *x2==*y2 && w1<w2) || (*x1==*y1 && *x2==*y2 && w1==w2 && r1<r2));
}
};
-////////////////////
+//struct EdgeCompare2{
+//bool operator()(Edge e1, Edge e2) const {
+// assert(!e1.isNull() && !e2.isNull());
+// return (e1.getRandId()<e2.getRandId());
+//}
+//};
+
//this is used to color vertices
//during DFS
//a private method for doing DFS traversal of graph
//this is used in determining the reverse topological sort
//of the graph
- void DFS_Visit(Node *nd, std::vector<Node *> &toReturn) const;
+ void DFS_Visit(Node *nd, std::vector<Node *> &toReturn);
//Its a variation of DFS to get the backedges in the graph
//We get back edges by associating a time
std::vector<Edge > &be,
std::map<Node *, Color> &clr,
std::map<Node *, int> &d,
- int &time) const;
+ int &time);
public:
typedef nodeMapTy::iterator elementIterator;
//having an edge simply means that there is an edge in the graph
//which has same endpoints as the given edge
//it may possibly have different weight though
- bool hasEdge(Edge ed) const;
+ bool hasEdge(Edge ed);
//check whether graph has an edge, with a given wt
- bool hasEdgeAndWt(Edge ed) const;
+ bool hasEdgeAndWt(Edge ed);
//get the list of successor nodes
- std::vector<Node *> getSuccNodes(Node *nd) const;
+ std::vector<Node *> getSuccNodes(Node *nd);
//get the number of outgoing edges
int getNumberOfOutgoingEdges(Node *nd) const;
//get the list of predecessor nodes
- std::vector<Node *> getPredNodes(Node *nd) const;
+ std::vector<Node *> getPredNodes(Node *nd);
//to get the no of incoming edges
- int getNumberOfIncomingEdges(Node *nd) const;
+ int getNumberOfIncomingEdges(Node *nd);
//get the list of all the vertices in graph
std::vector<Node *> getAllNodes() const;
//get a list of nodes in the graph
//in r-topological sorted order
//note that we assumed graph to be connected
- std::vector<Node *> reverseTopologicalSort() const;
+ std::vector<Node *> reverseTopologicalSort();
//reverse the sign of weights on edges
//this way, max-spanning tree could be obtained
void printGraph();
//get a vector of back edges in the graph
- void getBackEdges(std::vector<Edge> &be) const;
+ void getBackEdges(std::vector<Edge> &be, std::map<Node *, int> &d);
+
+ nodeList &sortNodeList(Node *par, nodeList &nl, std::vector<Edge> &be);
//Get the Maximal spanning tree (also a graph)
//of the graph
//get the nodeList adjacent to a node
//a nodeList element contains a node, and the weight
//corresponding to the edge for that element
- inline const nodeList &getNodeList(Node *nd) const {
- constElementIterator nli = nodes.find(nd);
+ inline nodeList &getNodeList(Node *nd) {
+ elementIterator nli = nodes.find(nd);
assert(nli != nodes.end() && "Node must be in nodes map");
- return nli->second;
+ return nodes[nd];//sortNodeList(nd, nli->second);
}
-
- inline nodeList &getNodeList(Node *nd) {
+
+ nodeList &getSortedNodeList(Node *nd, std::vector<Edge> &be) {
elementIterator nli = nodes.find(nd);
assert(nli != nodes.end() && "Node must be in nodes map");
- return nli->second;
+ return sortNodeList(nd, nodes[nd], be);
}
-
+
//get the root of the graph
inline Node *getRoot() {return strt; }
inline Node * const getRoot() const {return strt; }
//get the code to be inserted on the edge
//This is determined from cond (1-6)
- //<<<<<<< Graph.h
void getCode(Instruction *a, Instruction *b, Function *M, BasicBlock *BB,
- int numPaths, int MethNo);
- //=======
- //void getCode(Instruction *a, Instruction *b, Function *F, BasicBlock *BB);
- //>>>>>>> 1.4
+ std::vector<Value *> &retVec);
};
//Do graph processing: to determine minimal edge increments,
//appropriate code insertions etc and insert the code at
//appropriate locations
-void processGraph(Graph &g, Instruction *rInst, Instruction *countInst, std::vector<Edge> &be, std::vector<Edge> &stDummy, std::vector<Edge> &exDummy, int n);
+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);
//print the graph (for debugging)
void printGraph(Graph &g);
//void printGraph(const Graph g);
//insert a basic block with appropriate code
//along a given edge
-void insertBB(Edge ed, getEdgeCode *edgeCode, Instruction *rInst, Instruction *countInst, int n, int Methno);
+void insertBB(Edge ed, getEdgeCode *edgeCode, Instruction *rInst, Instruction *countInst, int n, int Methno, Value *threshold);
//Insert the initialization code in the top BB
//this includes initializing r, and count
//number of that path
//Count is an array, where Count[k] represents
//the number of executions of path k
-void insertInTopBB(BasicBlock *front, int k, Instruction *rVar, Instruction *countVar);
+void insertInTopBB(BasicBlock *front, int k, Instruction *rVar, Instruction *countVar, Value *threshold);
//Add dummy edges corresponding to the back edges
//If a->b is a backedge
//such that if we traverse along any path from root to exit, and
//add up the edge values, we get a path number that uniquely
//refers to the path we travelled
-int valueAssignmentToEdges(Graph& g);
+int valueAssignmentToEdges(Graph& g, std::map<Node *, int> nodePriority,
+ std::vector<Edge> &be);
void getBBtrace(std::vector<BasicBlock *> &vBB, int pathNo, Function *M);
#endif
projects / oota-llvm.git / blobdiff