-//===--Graph.cpp--- implements Graph class ---------------- ------*- C++ -*--=//
+//===-- Graph.cpp - Implements Graph class --------------------------------===//
+//
+// The LLVM Compiler Infrastructure
//
-// This implements Graph for helping in trace generation
-// This graph gets used by "ProfilePaths" class
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This implements Graph for helping in trace generation This graph gets used by
+// "ProfilePaths" class.
//
//===----------------------------------------------------------------------===//
-#include "llvm/Transforms/Instrumentation/Graph.h"
-#include "llvm/iTerminators.h"
-#include "llvm/BasicBlock.h"
+#include "Graph.h"
+#include "llvm/Instructions.h"
+#include "llvm/Support/Debug.h"
#include <algorithm>
-#include <iostream>
-//using std::list;
-//using std::set;
-using std::map;
using std::vector;
-using std::cerr;
+
+namespace llvm {
const graphListElement *findNodeInList(const Graph::nodeList &NL,
Node *N) {
return false;
Node *nd2=ed.getSecond();
- nodeList nli = nodes[ed.getFirst()];//getNodeList(ed.getFirst());
+ nodeList &nli = nodes[ed.getFirst()];//getNodeList(ed.getFirst());
for(nodeList::iterator NI=nli.begin(), NE=nli.end(); NI!=NE; ++NI)
if(*NI->element == *nd2 && ed.getWeight()==NI->weight)
//add an edge
//this adds an edge ONLY when
-//the edge to be added doesn not already exist
+//the edge to be added does not already exist
//we "equate" two edges here only with their
//end points
void Graph::addEdge(Edge ed, int w){
static void printNode(Node *nd){
- cerr<<"Node:"<<nd->getElement()->getName()<<"\n";
+ std::cerr<<"Node:"<<nd->getElement()->getName()<<"\n";
}
//Get the Maximal spanning tree (also a graph)
vector<Node *> vt;
- map<Node*, Node* > parent;
- map<Node*, int > ed_weight;
+ std::map<Node*, Node* > parent;
+ std::map<Node*, int > ed_weight;
//initialize: wt(root)=0, wt(others)=infinity
//parent(root)=NULL, parent(others) not defined (but not null)
//keep pulling out vertex of min wt from vt
while(!vt.empty()){
- Node *u=*(min_element(vt.begin(), vt.end(), compare_nodes()));
- DEBUG(cerr<<"popped wt"<<(u)->getWeight()<<"\n";
+ Node *u=*(std::min_element(vt.begin(), vt.end(), compare_nodes()));
+ DEBUG(std::cerr<<"popped wt"<<(u)->getWeight()<<"\n";
printNode(u));
if(parent[u]!=NULL){ //so not root
Edge edge(parent[u],u, ed_weight[u]); //assign edge in spanning tree
st->addEdge(edge,ed_weight[u]);
- DEBUG(cerr<<"added:\n";
+ DEBUG(std::cerr<<"added:\n";
printEdge(edge));
}
//assign wt(v) to all adjacent vertices v of u
//only if v is in vt
- Graph::nodeList nl=getNodeList(u);
+ Graph::nodeList &nl = getNodeList(u);
for(nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){
Node *v=NI->element;
int weight=-NI->weight;
break;
}
}
- DEBUG(cerr<<"wt:v->wt"<<weight<<":"<<v->getWeight()<<"\n";
- printNode(v);cerr<<"node wt:"<<(*v).weight<<"\n");
+ DEBUG(std::cerr<<"wt:v->wt"<<weight<<":"<<v->getWeight()<<"\n";
+ printNode(v);std::cerr<<"node wt:"<<(*v).weight<<"\n");
//so if v in in vt, change wt(v) to wt(u->v)
//only if wt(u->v)<wt(v)
ed_weight[v]=weight;
v->setWeight(weight);
- DEBUG(cerr<<v->getWeight()<<":Set weight------\n";
+ DEBUG(std::cerr<<v->getWeight()<<":Set weight------\n";
printGraph();
printEdge(Edge(u,v,weight)));
}
//print the graph (for debugging)
void Graph::printGraph(){
vector<Node *> lt=getAllNodes();
- cerr<<"Graph---------------------\n";
+ std::cerr<<"Graph---------------------\n";
for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
- cerr<<((*LI)->getElement())->getName()<<"->";
- Graph::nodeList nl=getNodeList(*LI);
+ std::cerr<<((*LI)->getElement())->getName()<<"->";
+ Graph::nodeList &nl = getNodeList(*LI);
for(Graph::nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){
- cerr<<":"<<"("<<(NI->element->getElement())
+ std::cerr<<":"<<"("<<(NI->element->getElement())
->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")";
}
- cerr<<"--------\n";
+ std::cerr<<"--------\n";
}
}
vector<Node* > allNodes=getAllNodes();
for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
++NI) {
- nodeList nl=getNodeList(*NI);
+ nodeList &nl = getNodeList(*NI);
for(nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE; ++NLI){
Edge ed(NLI->element, *NI, NLI->weight);
if(!hasEdgeAndWt(ed)){
- DEBUG(cerr<<"######doesn't hv\n";
+ DEBUG(std::cerr<<"######doesn't hv\n";
printEdge(ed));
addEdgeForce(ed);
}
//reverse the sign of weights on edges
//this way, max-spanning tree could be obtained
-//usin min-spanning tree, and vice versa
+//using min-spanning tree, and vice versa
void Graph::reverseWts(){
vector<Node *> allNodes=getAllNodes();
for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
++NI) {
- nodeList node_list=getNodeList(*NI);
+ nodeList &node_list = getNodeList(*NI);
for(nodeList::iterator NLI=nodes[*NI].begin(), NLE=nodes[*NI].end();
NLI!=NLE; ++NLI)
NLI->weight=-NLI->weight;
//have been visited
//So we have a back edge when we meet a successor of
//a node with smaller time, and GREY color
-void Graph::getBackEdges(vector<Edge > &be, map<Node *, int> &d){
- map<Node *, Color > color;
+void Graph::getBackEdges(vector<Edge > &be, std::map<Node *, int> &d){
+ std::map<Node *, Color > color;
int time=0;
getBackEdgesVisit(getRoot(), be, color, d, time);
//helper function to get back edges: it is called by
//the "getBackEdges" function above
void Graph::getBackEdgesVisit(Node *u, vector<Edge > &be,
- map<Node *, Color > &color,
- map<Node *, int > &d, int &time) {
+ std::map<Node *, Color > &color,
+ std::map<Node *, int > &d, int &time) {
color[u]=GREY;
time++;
d[u]=time;
color[u]=BLACK;//done with visiting the node and its neighbors
}
-
+} // End llvm namespace
projects / oota-llvm.git / blobdiff