additions and bug fixes

llvm-svn: 2794

5 files changed, 1395 insertions, 445 deletions

diff --git a/llvm/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp b/llvm/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp
index 1c0970537a7..efbd5c86c6f 100644
--- a/llvm/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp
+++ b/llvm/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp
@@ -7,7 +7,7 @@
 //top block of cfg
 //===----------------------------------------------------------------------===//
 
-#include "Graph.h"
+#include "llvm/Transforms/Instrumentation/Graph.h"
 #include "llvm/BasicBlock.h"
 #include "llvm/Constants.h"
 #include "llvm/DerivedTypes.h"
@@ -16,15 +16,89 @@
 #include "llvm/iOther.h"
 #include "llvm/iOperators.h"
 #include "llvm/iPHINode.h"
+#include "llvm/Module.h"
+#include "llvm/SymbolTable.h"
+#include "llvm/GlobalVariable.h"
+#include "llvm/Constants.h"//llvm/ConstantVals.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Function.h"
+#include <string.h>
+#include <stdio.h>
+#include <iostream>
+
+#define INSERT_LOAD_COUNT
+#define INSERT_STORE
 
 using std::vector;
 
+
+void getTriggerCode(Module *M, BasicBlock *BB, int MethNo, Value *pathNo, 
+		    Value *cnt){
+  //  return;
+  //cerr<<"In trigger code"<<endl;
+  static int i=-1;
+  i++;
+  char gstr[100];
+  sprintf(gstr,"globalVar%d",i);
+  std::string globalVarName=gstr;
+  SymbolTable *ST = M->getSymbolTable();
+  vector<const Type*> args;
+  args.push_back(PointerType::get(Type::SByteTy));
+  args.push_back(Type::IntTy);
+  args.push_back(Type::IntTy);
+  args.push_back(Type::IntTy);
+  const FunctionType *MTy =
+    FunctionType::get(Type::VoidTy, args, false);
+
+  //  Function *triggerMeth = M->getOrInsertFunction("trigger", MTy);
+  Function *trigMeth = M->getOrInsertFunction("trigger", MTy);
+  assert(trigMeth && "trigger method could not be inserted!");
+  //if (Value *triggerMeth = ST->lookup(PointerType::get(MTy), "trigger")) {
+  //Function *trigMeth = cast<Function>(triggerMeth);
+  vector<Value *> trargs;
+
+  //pred_iterator piter=BB->pred_begin();
+  std::string predName=BB->getName();
+  Constant *bbName=ConstantArray::get(predName);//BB->getName());
+  GlobalVariable *gbl=new GlobalVariable(ArrayType::get(Type::SByteTy, 
+							predName.size()+1), 
+					 true, true, bbName, gstr);
+  M->getGlobalList().push_back(gbl);
+
+  vector<Value *> elargs;
+  elargs.push_back(ConstantUInt::get(Type::UIntTy, 0));
+  elargs.push_back(ConstantUInt::get(Type::UIntTy, 0));
+
+  Instruction *getElmntInst=new GetElementPtrInst(gbl,elargs,"elmntInst");
+
+  //trargs.push_back(ConstantArray::get(BB->getName()));
+  trargs.push_back(getElmntInst);
+  trargs.push_back(ConstantSInt::get(Type::IntTy,MethNo));
+    
+  //trargs.push_back(ConstantSInt::get(Type::IntTy,-1));//erase this
+  trargs.push_back(pathNo);
+  trargs.push_back(cnt);
+  Instruction *callInst=new CallInst(trigMeth,trargs);
+
+  BasicBlock::InstListType& instList=BB->getInstList();
+  BasicBlock::iterator here=instList.begin();
+  here = ++instList.insert(here, getElmntInst);
+  instList.insert(here,callInst);
+  //}
+  //else{
+  //insert trigger method
+    
+  //assert(0&&"No method trigger");
+  //}
+}
+
+
 //get the code to be inserted on the edge
 //This is determined from cond (1-6)
 void getEdgeCode::getCode(Instruction *rInst, 
 			  Instruction *countInst, 
 			  Function *M, 
-			  BasicBlock *BB){
+			  BasicBlock *BB, int numPaths, int MethNo){
   
   BasicBlock::InstListType& instList=BB->getInstList();
   BasicBlock::iterator here=instList.begin();
@@ -33,35 +107,46 @@ void getEdgeCode::getCode(Instruction *rInst,
   switch(cond){
   case 1:{
     Value *val=ConstantSInt::get(Type::IntTy,inc);
+#ifdef INSERT_STORE
     Instruction *stInst=new StoreInst(val, rInst);
-    here=++instList.insert(here,stInst);
+    here = ++instList.insert(here,stInst);
+#endif
     break;
     }
 
   //case: r=0 to be inserted
   case 2:{
     Value *val=ConstantSInt::get(Type::IntTy,0);
+#ifdef INSERT_STORE
     Instruction *stInst=new StoreInst(val, rInst);
-    here=++instList.insert(here,stInst);
+    here = ++instList.insert(here,stInst);
+#endif
     break;
   }
     
   //r+=k
   case 3:{
+    
     Instruction *ldInst=new LoadInst(rInst, "ti1");
     Value *val=ConstantSInt::get(Type::IntTy,inc);
     Instruction *addIn=BinaryOperator::
       create(Instruction::Add, ldInst, val,"ti2");
-    
+#ifdef INSERT_STORE
     Instruction *stInst=new StoreInst(addIn, rInst);
-    here=++instList.insert(here,ldInst);
-    here=++instList.insert(here,addIn);
-    here=++instList.insert(here,stInst);
+#endif
+    here = ++instList.insert(here,ldInst);
+    here = ++instList.insert(here,addIn);
+#ifdef INSERT_STORE
+    here = ++instList.insert(here,stInst);
+#endif
     break;
   }
 
   //count[inc]++
   case 4:{
+    
+    assert(inc>=0 && inc<=numPaths && "inc out of bound!");
+   
     Instruction *ldInst=new 
       LoadInst(countInst,vector<Value *>
 	       (1,ConstantUInt::get(Type::UIntTy, inc)), "ti1");
@@ -69,53 +154,76 @@ void getEdgeCode::getCode(Instruction *rInst,
     Instruction *addIn=BinaryOperator::
       create(Instruction::Add, ldInst, val,"ti2");
 
+    //insert trigger
+    getTriggerCode(M->getParent(), BB, MethNo, 
+		   ConstantSInt::get(Type::IntTy,inc), addIn);
+    here=instList.begin();
+    //end trigger code
+
     assert(inc>=0 && "IT MUST BE POSITIVE NOW");
+#ifdef INSERT_STORE
     Instruction *stInst=new 
       StoreInst(addIn, countInst, vector<Value *>
 		(1, ConstantUInt::get(Type::UIntTy,inc)));
-    
-    here=++instList.insert(here,ldInst);
-    here=++instList.insert(here,addIn);
-    here=++instList.insert(here,stInst);
+#endif
+    here = ++instList.insert(here,ldInst);
+    here = ++instList.insert(here,addIn);
+#ifdef INSERT_STORE
+    here = ++instList.insert(here,stInst);
+#endif
     break;
   }
 
   //case: count[r+inc]++
   case 5:{
+    
     //ti1=inc+r
     Instruction *ldIndex=new LoadInst(rInst, "ti1");
     Value *val=ConstantSInt::get(Type::IntTy,inc);
     Instruction *addIndex=BinaryOperator::
       create(Instruction::Add, ldIndex, val,"ti2");
-    
+    //erase following 1 line
+    //Value *valtemp=ConstantSInt::get(Type::IntTy,999);
     //now load count[addIndex]
+    
     Instruction *castInst=new CastInst(addIndex, 
 				       Type::UIntTy,"ctin");
     Instruction *ldInst=new 
       LoadInst(countInst, vector<Value *>(1,castInst), "ti3");
     Value *cons=ConstantSInt::get(Type::IntTy,1);
-    
     //count[addIndex]++
     Instruction *addIn=BinaryOperator::
       create(Instruction::Add, ldInst, cons,"ti4");
+    
+    //insert trigger
+    getTriggerCode(M->getParent(), BB, MethNo, addIndex, addIn);
+    here=instList.begin();
+    //end trigger code
+    
+#ifdef INSERT_STORE
+    ///*
     Instruction *stInst=new 
       StoreInst(addIn, countInst, 
 		vector<Value *>(1,castInst));
-    
-    here=++instList.insert(here,ldIndex);
-    here=++instList.insert(here,addIndex);
-    here=++instList.insert(here,castInst);
-    here=++instList.insert(here,ldInst);
-    here=++instList.insert(here,addIn);
-    here=++instList.insert(here,stInst);
+    //*/
+#endif
+    here = ++instList.insert(here,ldIndex);
+    here = ++instList.insert(here,addIndex);
+    here = ++instList.insert(here,castInst);
+    here = ++instList.insert(here,ldInst);
+    here = ++instList.insert(here,addIn);
+#ifdef INSERT_STORE
+    here = ++instList.insert(here,stInst);
+#endif
     break;
   }
 
     //case: count[r]+
   case 6:{
+    
     //ti1=inc+r
     Instruction *ldIndex=new LoadInst(rInst, "ti1");
-
+    
     //now load count[addIndex]
     Instruction *castInst2=new 
       CastInst(ldIndex, Type::UIntTy,"ctin");
@@ -126,27 +234,34 @@ void getEdgeCode::getCode(Instruction *rInst,
     //count[addIndex]++
     Instruction *addIn=BinaryOperator::
       create(Instruction::Add, ldInst, cons,"ti3"); 
+
+    //insert trigger
+    getTriggerCode(M->getParent(), BB, MethNo, ldIndex, addIn);
+    here=instList.begin();
+    //end trigger code
+#ifdef INSERT_STORE
     Instruction *stInst=new 
       StoreInst(addIn, countInst, vector<Value *>(1,castInst2));
-    
-    here=++instList.insert(here,ldIndex);
-    here=++instList.insert(here,castInst2);
-    here=++instList.insert(here,ldInst);
-    here=++instList.insert(here,addIn);
-    here=++instList.insert(here,stInst);
+#endif
+    here = ++instList.insert(here,ldIndex);
+    here = ++instList.insert(here,castInst2);
+    here = instList.insert(here,ldInst);
+    here = instList.insert(here,addIn);
+#ifdef INSERT_STORE
+    here = instList.insert(here,stInst);
+#endif
     break;
   }
     
   }
   //now check for cdIn and cdOut
   //first put cdOut
-  if(cdOut!=NULL){
-    cdOut->getCode(rInst, countInst, M, BB);
-  }
   if(cdIn!=NULL){
-    cdIn->getCode(rInst, countInst, M, BB);
+    cdIn->getCode(rInst, countInst, M, BB, numPaths, MethNo);
+  }
+  if(cdOut!=NULL){
+    cdOut->getCode(rInst, countInst, M, BB, numPaths, MethNo);
   }
-
 }
 
 
@@ -179,6 +294,7 @@ void insertInTopBB(BasicBlock *front,
   here=++front->getInstList().insert(here,countVar);
   
   //Initialize Count[...] with 0
+
   for(int i=0;i<k; i++){
     Instruction *stInstrC=new 
       StoreInst(ConstantInt::get(Type::IntTy, 0), 
@@ -186,8 +302,8 @@ void insertInTopBB(BasicBlock *front,
 		(1,ConstantUInt::get(Type::UIntTy, i))); 
     here=++front->getInstList().insert(here,stInstrC);
   }
-  
-  here=++front->getInstList().insert(here,stInstr);
+
+  here = ++front->getInstList().insert(here,stInstr);
 }
 
 
@@ -196,21 +312,30 @@ void insertInTopBB(BasicBlock *front,
 void insertBB(Edge ed,
 	      getEdgeCode *edgeCode, 
 	      Instruction *rInst, 
-	      Instruction *countInst){
-
+	      Instruction *countInst, 
+	      int numPaths, int Methno){
+  static int i=-1;
+  i++;
   BasicBlock* BB1=ed.getFirst()->getElement();
   BasicBlock* BB2=ed.getSecond()->getElement();
   
-  DEBUG(cerr << "Edges with codes ######################\n";
-        cerr << BB1->getName() << "->" << BB2->getName() << "\n";
-        cerr << "########################\n");
+#ifdef DEBUG_PATH_PROFILES
+  //debugging info
+  cerr<<"Edges with codes ######################\n";
+  cerr<<BB1->getName()<<"->"<<BB2->getName()<<"\n";
+  cerr<<"########################\n";
+#endif
+  
+  char counterstr[100];
+  sprintf(counterstr,"counter%d",i);
+  std::string ctr=counterstr;
 
   //We need to insert a BB between BB1 and BB2 
   TerminatorInst *TI=BB1->getTerminator();
-  BasicBlock *newBB=new BasicBlock("counter", BB1->getParent());
+  BasicBlock *newBB=new BasicBlock(ctr, BB1->getParent());
 
   //get code for the new BB
-  edgeCode->getCode(rInst, countInst, BB1->getParent(), newBB);
+  edgeCode->getCode(rInst, countInst, BB1->getParent(), newBB, numPaths, Methno);
  
   //Is terminator a branch instruction?
   //then we need to change branch destinations to include new BB
@@ -223,32 +348,26 @@ void insertBB(Edge ed,
     newBB->getInstList().push_back(newBI2);
   }
   else{
-    Value *cond=BI->getCondition();
-    BasicBlock *fB, *tB;
-   
-    if (BI->getSuccessor(0) == BB2){
-      tB=newBB;
-      fB=BI->getSuccessor(1);
-    } else {
-      fB=newBB;
-      tB=BI->getSuccessor(0);
-    }
-   
-    BB1->getInstList().pop_back();
-    BB1->getInstList().push_back(new BranchInst(tB,fB,cond));
-    newBB->getInstList().push_back(new BranchInst(BB2));
+      if(BI->getSuccessor(0)==BB2)
+      BI->setSuccessor(0, newBB);
+    
+    if(BI->getSuccessor(1)==BB2)
+      BI->setSuccessor(1, newBB);
+
+    Instruction *newBI2=new BranchInst(BB2);
+    newBB->getInstList().push_back(newBI2);
   }
   
-  //now iterate over BB2, and set its Phi nodes right
+  //get code for the new BB
+   //now iterate over BB2, and set its Phi nodes right
   for(BasicBlock::iterator BB2Inst = BB2->begin(), BBend = BB2->end(); 
       BB2Inst != BBend; ++BB2Inst){
    
     if(PHINode *phiInst=dyn_cast<PHINode>(&*BB2Inst)){
-      DEBUG(cerr<<"YYYYYYYYYYYYYYYYY\n");
-
       int bbIndex=phiInst->getBasicBlockIndex(BB1);
-      if(bbIndex>=0)
-	phiInst->setIncomingBlock(bbIndex, newBB);
+      assert(bbIndex>=0);
+      phiInst->setIncomingBlock(bbIndex, newBB);
     }
   }
 }
+
diff --git a/llvm/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp b/llvm/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp
index 0e7bce06b4d..585aec0a146 100644
--- a/llvm/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp
+++ b/llvm/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp
@@ -5,18 +5,18 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "Graph.h"
+#include "llvm/Transforms/Instrumentation/Graph.h"
 #include "llvm/BasicBlock.h"
 #include <algorithm>
 #include <iostream>
 
-using std::list;
-using std::set;
+//using std::list;
+//using std::set;
 using std::map;
 using std::vector;
 using std::cerr;
 
-static const graphListElement *findNodeInList(const Graph::nodeList &NL,
+const graphListElement *findNodeInList(const Graph::nodeList &NL,
 					      Node *N) {
   for(Graph::nodeList::const_iterator NI = NL.begin(), NE=NL.end(); NI != NE; 
       ++NI)
@@ -25,7 +25,7 @@ static const graphListElement *findNodeInList(const Graph::nodeList &NL,
   return 0;
 }
 
-static graphListElement *findNodeInList(Graph::nodeList &NL, Node *N) {
+graphListElement *findNodeInList(Graph::nodeList &NL, Node *N) {
   for(Graph::nodeList::iterator NI = NL.begin(), NE=NL.end(); NI != NE; ++NI)
     if (*NI->element== *N)
       return &*NI;
@@ -33,17 +33,19 @@ static graphListElement *findNodeInList(Graph::nodeList &NL, Node *N) {
 }
 
 //graph constructor with root and exit specified
-Graph::Graph(std::set<Node*> n, std::set<Edge> e, 
+Graph::Graph(std::vector<Node*> n, std::vector<Edge> e, 
 	     Node *rt, Node *lt){
   strt=rt;
   ext=lt;
-  for(set<Node* >::iterator x=n.begin(), en=n.end(); x!=en; ++x)
-    nodes[*x] = list<graphListElement>();
+  for(vector<Node* >::iterator x=n.begin(), en=n.end(); x!=en; ++x)
+    //nodes[*x] = list<graphListElement>();
+    nodes[*x] = vector<graphListElement>();
 
-  for(set<Edge >::iterator x=e.begin(), en=e.end(); x!=en; ++x){
+  for(vector<Edge >::iterator x=e.begin(), en=e.end(); x!=en; ++x){
     Edge ee=*x;
     int w=ee.getWeight();
-    nodes[ee.getFirst()].push_front(graphListElement(ee.getSecond(),w));   
+    //nodes[ee.getFirst()].push_front(graphListElement(ee.getSecond(),w, ee.getRandId()));   
+    nodes[ee.getFirst()].push_back(graphListElement(ee.getSecond(),w, ee.getRandId()));
   }
   
 }
@@ -83,14 +85,14 @@ bool Graph::hasEdgeAndWt(Edge ed) const{
 
 //add a node
 void Graph::addNode(Node *nd){
-  list<Node *> lt=getAllNodes();
+  vector<Node *> lt=getAllNodes();
 
-  for(list<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE;++LI){
+  for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE;++LI){
     if(**LI==*nd)
       return;
   }
-
-  nodes[nd] = list<graphListElement>();
+  //chng
+  nodes[nd] =vector<graphListElement>(); //list<graphListElement>();
 }
 
 //add an edge
@@ -105,7 +107,10 @@ void Graph::addEdge(Edge ed, int w){
   if(findNodeInList(nodes[ed.getFirst()], nd2))
     return;
  
-  ndList.push_front(graphListElement(nd2,w));
+  //ndList.push_front(graphListElement(nd2,w, ed.getRandId()));
+  ndList.push_back(graphListElement(nd2,w, ed.getRandId()));//chng
+
+  //sort(ndList.begin(), ndList.end(), NodeListSort());
 }
 
 //add an edge EVEN IF such an edge already exists
@@ -113,8 +118,12 @@ void Graph::addEdge(Edge ed, int w){
 //which does happen when we add dummy edges
 //to the graph, for compensating for back-edges
 void Graph::addEdgeForce(Edge ed){
-  nodes[ed.getFirst()].push_front(graphListElement(ed.getSecond(),
-						   ed.getWeight()));
+  //nodes[ed.getFirst()].push_front(graphListElement(ed.getSecond(),
+  //ed.getWeight(), ed.getRandId()));
+  nodes[ed.getFirst()].push_back
+    (graphListElement(ed.getSecond(), ed.getWeight(), ed.getRandId()));
+
+  //sort(nodes[ed.getFirst()].begin(), nodes[ed.getFirst()].end(), NodeListSort());
 }
 
 //remove an edge
@@ -132,6 +141,21 @@ void Graph::removeEdge(Edge ed){
   }
 }
 
+//remove an edge with a given wt
+//Note that it removes just one edge,
+//the first edge that is encountered
+void Graph::removeEdgeWithWt(Edge ed){
+  nodeList &ndList = nodes[ed.getFirst()];
+  Node &nd2 = *ed.getSecond();
+
+  for(nodeList::iterator NI=ndList.begin(), NE=ndList.end(); NI!=NE ;++NI) {
+    if(*NI->element == nd2 && NI->weight==ed.getWeight()) {
+      ndList.erase(NI);
+      break;
+    }
+  }
+}
+
 //set the weight of an edge
 void Graph::setWeight(Edge ed){
   graphListElement *El = findNodeInList(nodes[ed.getFirst()], ed.getSecond());
@@ -142,21 +166,34 @@ void Graph::setWeight(Edge ed){
 
 
 //get the list of successor nodes
-list<Node *> Graph::getSuccNodes(Node *nd) const {
+vector<Node *> Graph::getSuccNodes(Node *nd) const {
   nodeMapTy::const_iterator nli = nodes.find(nd);
   assert(nli != nodes.end() && "Node must be in nodes map");
   const nodeList &nl = nli->second;
 
-  list<Node *> lt;
+  vector<Node *> lt;
   for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI)
     lt.push_back(NI->element);
 
   return lt;
 }
 
+//get the number of outgoing edges
+int Graph::getNumberOfOutgoingEdges(Node *nd) const {
+  nodeMapTy::const_iterator nli = nodes.find(nd);
+  assert(nli != nodes.end() && "Node must be in nodes map");
+  const nodeList &nl = nli->second;
+
+  int count=0;
+  for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI)
+    count++;
+
+  return count;
+}
+
 //get the list of predecessor nodes
-list<Node *> Graph::getPredNodes(Node *nd) const{
-  list<Node *> lt;
+vector<Node *> Graph::getPredNodes(Node *nd) const{
+  vector<Node *> lt;
   for(nodeMapTy::const_iterator EI=nodes.begin(), EE=nodes.end(); EI!=EE ;++EI){
     Node *lnode=EI->first;
     const nodeList &nl = getNodeList(lnode);
@@ -167,15 +204,37 @@ list<Node *> Graph::getPredNodes(Node *nd) const{
   return lt;
 }
 
+//get the number of predecessor nodes
+int Graph::getNumberOfIncomingEdges(Node *nd) const{
+  int count=0;
+  for(nodeMapTy::const_iterator EI=nodes.begin(), EE=nodes.end(); EI!=EE ;++EI){
+    Node *lnode=EI->first;
+    const nodeList &nl = getNodeList(lnode);
+    for(Graph::nodeList::const_iterator NI = nl.begin(), NE=nl.end(); NI != NE; 
+	++NI)
+      if (*NI->element== *nd)
+	count++;
+  }
+  return count;
+}
+
 //get the list of all the vertices in graph
-list<Node *> Graph::getAllNodes() const{
-  list<Node *> lt;
+vector<Node *> Graph::getAllNodes() const{
+  vector<Node *> lt;
   for(nodeMapTy::const_iterator x=nodes.begin(), en=nodes.end(); x != en; ++x)
     lt.push_back(x->first);
 
   return lt;
 }
 
+//get the list of all the vertices in graph
+vector<Node *> Graph::getAllNodes(){
+  vector<Node *> lt;
+  for(nodeMapTy::const_iterator x=nodes.begin(), en=nodes.end(); x != en; ++x)
+    lt.push_back(x->first);
+
+  return lt;
+}
 
 //class to compare two nodes in graph
 //based on their wt: this is used in
@@ -198,7 +257,7 @@ Graph* Graph::getMaxSpanningTree(){
  
   Graph *st=new Graph();//max spanning tree, undirected edges
   int inf=9999999;//largest key
-  list<Node *> lt = getAllNodes();
+  vector<Node *> lt = getAllNodes();
   
   //initially put all vertices in vector vt
   //assign wt(root)=0
@@ -221,7 +280,7 @@ Graph* Graph::getMaxSpanningTree(){
 
   //initialize: wt(root)=0, wt(others)=infinity
   //parent(root)=NULL, parent(others) not defined (but not null)
-  for(list<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
+  for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
     Node *thisNode=*LI;
     if(*thisNode == *getRoot()){
       thisNode->setWeight(0);
@@ -295,9 +354,9 @@ Graph* Graph::getMaxSpanningTree(){
 
 //print the graph (for debugging)   
 void Graph::printGraph(){
-   list<Node *> lt=getAllNodes();
+   vector<Node *> lt=getAllNodes();
    cerr<<"Graph---------------------\n";
-   for(list<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
+   for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
      cerr<<((*LI)->getElement())->getName()<<"->";
      Graph::nodeList nl=getNodeList(*LI);
      for(Graph::nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){
@@ -312,10 +371,10 @@ void Graph::printGraph(){
 //get a list of nodes in the graph
 //in r-topological sorted order
 //note that we assumed graph to be connected
-list<Node *> Graph::reverseTopologicalSort() const{
-  list <Node *> toReturn;
-  list<Node *> lt=getAllNodes();
-  for(list<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
+vector<Node *> Graph::reverseTopologicalSort() const{
+  vector <Node *> toReturn;
+  vector<Node *> lt=getAllNodes();
+  for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
     if((*LI)->getWeight()!=GREY && (*LI)->getWeight()!=BLACK)
       DFS_Visit(*LI, toReturn);
   }
@@ -325,10 +384,10 @@ list<Node *> Graph::reverseTopologicalSort() const{
 //a private method for doing DFS traversal of graph
 //this is used in determining the reverse topological sort 
 //of the graph
-void Graph::DFS_Visit(Node *nd, list<Node *> &toReturn) const {
+void Graph::DFS_Visit(Node *nd, vector<Node *> &toReturn) const {
   nd->setWeight(GREY);
-  list<Node *> lt=getSuccNodes(nd);
-  for(list<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
+  vector<Node *> lt=getSuccNodes(nd);
+  for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
     if((*LI)->getWeight()!=GREY && (*LI)->getWeight()!=BLACK)
       DFS_Visit(*LI, toReturn);
   }
@@ -341,8 +400,8 @@ void Graph::DFS_Visit(Node *nd, list<Node *> &toReturn) const {
 //This is done by adding an edge
 //v->u for all existing edges u->v
 void Graph::makeUnDirectional(){
-  list<Node* > allNodes=getAllNodes();
-  for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
+  vector<Node* > allNodes=getAllNodes();
+  for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
       ++NI) {
     nodeList nl=getNodeList(*NI);
     for(nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE; ++NLI){
@@ -360,8 +419,8 @@ void Graph::makeUnDirectional(){
 //this way, max-spanning tree could be obtained
 //usin min-spanning tree, and vice versa
 void Graph::reverseWts(){
-  list<Node *> allNodes=getAllNodes();
-  for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
+  vector<Node *> allNodes=getAllNodes();
+  for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
       ++NI) {
     nodeList node_list=getNodeList(*NI);
     for(nodeList::iterator NLI=nodes[*NI].begin(), NLE=nodes[*NI].end(); 
@@ -385,9 +444,9 @@ void Graph::reverseWts(){
 void Graph::getBackEdges(vector<Edge > &be) const{
   map<Node *, Color > color;
   map<Node *, int > d;
-  list<Node *> allNodes=getAllNodes();
+  vector<Node *> allNodes=getAllNodes();
   int time=0;
-  for(list<Node *>::const_iterator NI=allNodes.begin(), NE=allNodes.end(); 
+  for(vector<Node *>::const_iterator NI=allNodes.begin(), NE=allNodes.end(); 
       NI!=NE; ++NI){
     if(color[*NI]!=GREY && color[*NI]!=BLACK)
       getBackEdgesVisit(*NI, be, color, d, time);
@@ -402,20 +461,24 @@ void Graph::getBackEdgesVisit(Node *u, vector<Edge > &be,
   color[u]=GREY;
   time++;
   d[u]=time;
-  list<Node *> succ_list=getSuccNodes(u);
 
-  for(list<Node *>::const_iterator v=succ_list.begin(), ve=succ_list.end(); 
-      v!=ve; ++v){
-    if(color[*v]!=GREY && color[*v]!=BLACK){
-      getBackEdgesVisit(*v, be, color, d, time);
+  vector<graphListElement> succ_list=getNodeList(u);
+  for(vector<graphListElement>::const_iterator vl=succ_list.begin(), 
+	ve=succ_list.end(); vl!=ve; ++vl){
+    Node *v=vl->element;
+  //  for(vector<Node *>::const_iterator v=succ_list.begin(), ve=succ_list.end(); 
+  //  v!=ve; ++v){
+
+    if(color[v]!=GREY && color[v]!=BLACK){
+      getBackEdgesVisit(v, be, color, d, time);
     }
 
     //now checking for d and f vals
-    if(color[*v]==GREY){
+    if(color[v]==GREY){
       //so v is ancestor of u if time of u > time of v
-      if(d[u] >= d[*v]){
-	Edge *ed=new Edge(u, *v);
-	if (!(*u == *getExit() && **v == *getRoot()))
+      if(d[u] >= d[v]){
+	Edge *ed=new Edge(u, v,vl->weight, vl->randId);
+	if (!(*u == *getExit() && *v == *getRoot()))
 	  be.push_back(*ed);      // choose the forward edges
       }
     }
diff --git a/llvm/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxiliary.cpp b/llvm/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxiliary.cpp
index b2c5445c450..1eadcb6c6ad 100644
--- a/llvm/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxiliary.cpp
+++ b/llvm/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxiliary.cpp
@@ -6,12 +6,15 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "Graph.h"
+#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
+#include "llvm/Function.h"
+#include "llvm/Pass.h"
 #include "llvm/BasicBlock.h"
+#include "llvm/Transforms/Instrumentation/Graph.h"
 #include <algorithm>
 #include <iostream>
 
-using std::list;
+//using std::list;
 using std::map;
 using std::vector;
 using std::cerr;
@@ -25,13 +28,13 @@ static bool edgesEqual(Edge  ed1, Edge ed2){
 static void getChords(vector<Edge > &chords, Graph &g, Graph st){
   //make sure the spanning tree is directional
   //iterate over ALL the edges of the graph
-  list<Node *> allNodes=g.getAllNodes();
-  for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
+  vector<Node *> allNodes=g.getAllNodes();
+  for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
       ++NI){
     Graph::nodeList node_list=g.getNodeList(*NI);
     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
 	NLI!=NLE; ++NLI){
-      Edge f(*NI, NLI->element,NLI->weight);
+      Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
       if(!(st.hasEdgeAndWt(f)))//addnl
 	chords.push_back(f);
     }
@@ -46,8 +49,8 @@ static void getChords(vector<Edge > &chords, Graph &g, Graph st){
 //the tree so that now, all edge directions in the tree match
 //the edge directions of corresponding edges in the directed graph
 static void removeTreeEdges(Graph &g, Graph& t){
-  list<Node* > allNodes=t.getAllNodes();
-  for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
+  vector<Node* > allNodes=t.getAllNodes();
+  for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
       ++NI){
     Graph::nodeList nl=t.getNodeList(*NI);
     for(Graph::nodeList::iterator NLI=nl.begin(), NLE=nl.end();	NLI!=NLE;++NLI){
@@ -64,18 +67,40 @@ static void removeTreeEdges(Graph &g, Graph& t){
 //add up the edge values, we get a path number that uniquely
 //refers to the path we travelled
 int valueAssignmentToEdges(Graph& g){
-  list<Node *> revtop=g.reverseTopologicalSort();
+  vector<Node *> revtop=g.reverseTopologicalSort();
+  /*
+  std::cerr<<"-----------Reverse topological sort\n";
+  for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); RI!=RE; ++RI){
+    std::cerr<<(*RI)->getElement()->getName()<<":";
+  }
+  std::cerr<<"\n----------------------"<<std::endl;
+  */
   map<Node *,int > NumPaths;
-  for(list<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); RI!=RE; ++RI){
+  for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); RI!=RE; ++RI){
     if(g.isLeaf(*RI))
       NumPaths[*RI]=1;
     else{
       NumPaths[*RI]=0;
-      list<Node *> succ=g.getSuccNodes(*RI);
-      for(list<Node *>::iterator SI=succ.begin(), SE=succ.end(); SI!=SE; ++SI){
-	Edge ed(*RI,*SI,NumPaths[*RI]);
-	g.setWeight(ed);
-	NumPaths[*RI]+=NumPaths[*SI];
+      /////
+      Graph::nodeList &nlist=g.getNodeList(*RI);
+      //sort nodelist by increasing order of numpaths
+      
+      int sz=nlist.size();
+      for(int i=0;i<sz-1; i++){
+	int min=i;
+	for(int j=i+1; j<sz; j++)
+	  if(NumPaths[nlist[j].element]<NumPaths[nlist[min].element]) min=j;
+	
+	graphListElement tempEl=nlist[min];
+	nlist[min]=nlist[i];
+	nlist[i]=tempEl;
+      }
+      //sorted now!
+
+      for(Graph::nodeList::iterator GLI=nlist.begin(), GLE=nlist.end();
+	  GLI!=GLE; ++GLI){
+	GLI->weight=NumPaths[*RI];
+	NumPaths[*RI]+=NumPaths[GLI->element];
       }
     }
   }
@@ -108,19 +133,26 @@ static int inc_Dir(Edge e, Edge f){
   return -1;
 }
 
+
 //used for getting edge increments (read comments above in inc_Dir)
 //inc_DFS is a modification of DFS 
-static void inc_DFS(Graph& g,Graph& t,map<Edge, int>& Increment, 
+static void inc_DFS(Graph& g,Graph& t,map<Edge, int, EdgeCompare>& Increment, 
 	     int events, Node *v, Edge e){
   
-  list<Node *> allNodes=t.getAllNodes();
-  
-  for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
+  vector<Node *> allNodes=t.getAllNodes();
+
+
+  //cerr<<"Called for\n";
+  //if(!e.isNull())
+  //printEdge(e);
+
+
+  for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
       ++NI){
     Graph::nodeList node_list=t.getNodeList(*NI);
     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
 	NLI!= NLE; ++NLI){
-      Edge f(*NI, NLI->element,NLI->weight);
+      Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
       if(!edgesEqual(f,e) && *v==*(f.getSecond())){
 	int dir_count=inc_Dir(e,f);
 	int wt=1*f.getWeight();
@@ -129,15 +161,15 @@ static void inc_DFS(Graph& g,Graph& t,map<Edge, int>& Increment,
     }
   }
 
-  for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
+  for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
       ++NI){
     Graph::nodeList node_list=t.getNodeList(*NI);
     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
 	NLI!=NLE; ++NLI){
-      Edge f(*NI, NLI->element,NLI->weight);
+      Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
       if(!edgesEqual(f,e) && *v==*(f.getFirst())){
       	int dir_count=inc_Dir(e,f);
-	int wt=1*f.getWeight();
+	int wt=f.getWeight();
 	inc_DFS(g,t, Increment, dir_count*events+wt, 
 		f.getSecond(), f);
       }
@@ -145,16 +177,18 @@ static void inc_DFS(Graph& g,Graph& t,map<Edge, int>& Increment,
   }
 
   allNodes=g.getAllNodes();
-  for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
+  for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
       ++NI){
     Graph::nodeList node_list=g.getNodeList(*NI);
     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
 	NLI!=NLE; ++NLI){
-      Edge f(*NI, NLI->element,NLI->weight);
+      Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
       if(!(t.hasEdgeAndWt(f)) && (*v==*(f.getSecond()) || 
 				  *v==*(f.getFirst()))){
 	int dir_count=inc_Dir(e,f);
 	Increment[f]+=dir_count*events;
+	//cerr<<"assigned "<<Increment[f]<<" to"<<endl;
+	//printEdge(f);
       }
     }
   }
@@ -164,19 +198,19 @@ static void inc_DFS(Graph& g,Graph& t,map<Edge, int>& Increment,
 //and assign them some values such that 
 //if we consider just this subset, it still represents
 //the path sum along any path in the graph
-static map<Edge, int> getEdgeIncrements(Graph& g, Graph& t){
+static map<Edge, int, EdgeCompare> getEdgeIncrements(Graph& g, Graph& t){
   //get all edges in g-t
-  map<Edge, int> Increment;
+  map<Edge, int, EdgeCompare> Increment;
 
-  list<Node *> allNodes=g.getAllNodes();
+  vector<Node *> allNodes=g.getAllNodes();
  
-  for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
+  for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
       ++NI){
     Graph::nodeList node_list=g.getNodeList(*NI);
     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
 	NLI!=NLE; ++NLI){
-      Edge ed(*NI, NLI->element,NLI->weight);
-      if(!(t.hasEdge(ed))){
+      Edge ed(*NI, NLI->element,NLI->weight,NLI->randId);
+      if(!(t.hasEdgeAndWt(ed))){
 	Increment[ed]=0;;
       }
     }
@@ -185,14 +219,13 @@ static map<Edge, int> getEdgeIncrements(Graph& g, Graph& t){
   Edge *ed=new Edge();
   inc_DFS(g,t,Increment, 0, g.getRoot(), *ed);
 
-
-  for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
+  for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
       ++NI){
     Graph::nodeList node_list=g.getNodeList(*NI);
     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
 	NLI!=NLE; ++NLI){
-      Edge ed(*NI, NLI->element,NLI->weight);
-      if(!(t.hasEdge(ed))){
+      Edge ed(*NI, NLI->element,NLI->weight, NLI->randId);
+      if(!(t.hasEdgeAndWt(ed))){
 	int wt=ed.getWeight();
 	Increment[ed]+=wt;
       }
@@ -202,13 +235,20 @@ static map<Edge, int> getEdgeIncrements(Graph& g, Graph& t){
   return Increment;
 }
 
+//push it up: TODO
+const graphListElement *findNodeInList(const Graph::nodeList &NL,
+					      Node *N);
+
+graphListElement *findNodeInList(Graph::nodeList &NL, Node *N);
+//end TODO
+
 //Based on edgeIncrements (above), now obtain
 //the kind of code to be inserted along an edge
 //The idea here is to minimize the computation
 //by inserting only the needed code
-static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *> &instr,
+static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *, EdgeCompare> &instr,
                               vector<Edge > &chords, 
-                              map<Edge,int> &edIncrements){
+                              map<Edge,int, EdgeCompare> &edIncrements){
 
   //Register initialization code
   vector<Node *> ws;
@@ -224,29 +264,34 @@ static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *> &instr,
       int edgeWt=nl->weight;
       Node *w=nl->element;
       //if chords has v->w
-      Edge ed(v,w);
-      
+      Edge ed(v,w, edgeWt, nl->randId);
+      //cerr<<"Assign:\n";
+      //printEdge(ed);
       bool hasEdge=false;
       for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
 	  CI!=CE && !hasEdge;++CI){
-	if(*CI==ed){
+	if(*CI==ed && CI->getWeight()==edgeWt){//modf
 	  hasEdge=true;
 	}
       }
-      if(hasEdge){
+
+      if(hasEdge){//so its a chord edge
 	getEdgeCode *edCd=new getEdgeCode();
 	edCd->setCond(1);
 	edCd->setInc(edIncrements[ed]);
 	instr[ed]=edCd;
+	//std::cerr<<"Case 1\n";
       }
-      else if((g.getPredNodes(w)).size()==1){
+      else if(g.getNumberOfIncomingEdges(w)==1){
 	ws.push_back(w);
+	//std::cerr<<"Added w\n";
       }
       else{
 	getEdgeCode *edCd=new getEdgeCode();
 	edCd->setCond(2);
 	edCd->setInc(0);
 	instr[ed]=edCd;
+	//std::cerr<<"Case 2\n";
       }
     }
   }
@@ -257,44 +302,55 @@ static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *> &instr,
   while(!ws.empty()) {
     Node *w=ws.back();
     ws.pop_back();
-    
-    //for each edge v->w
-    list<Node *> preds=g.getPredNodes(w);
-    for(list<Node *>::iterator pd=preds.begin(), pe=preds.end(); pd!=pe; ++pd){
-      Node *v=*pd;
-      //if chords has v->w
-    
-      Edge ed(v,w);
-      getEdgeCode *edCd=new getEdgeCode();
-      bool hasEdge=false;
-      for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
-	  ++CI){
-	if(*CI==ed){
-	  hasEdge=true;
-	  break;
+
+
+    ///////
+    //vector<Node *> lt;
+    vector<Node *> lllt=g.getAllNodes();
+    for(vector<Node *>::iterator EII=lllt.begin(); EII!=lllt.end() ;++EII){
+      Node *lnode=*EII;
+      Graph::nodeList &nl = g.getNodeList(lnode);
+      //cerr<<"Size:"<<lllt.size()<<"\n";
+      //cerr<<lnode->getElement()->getName()<<"\n";
+      graphListElement *N = findNodeInList(nl, w);
+      if (N){// lt.push_back(lnode);
+	
+	//Node *v=*pd;
+	//Node *v=N->element;
+	Node *v=lnode;
+	//if chords has v->w
+	
+	Edge ed(v,w, N->weight, N->randId);
+	getEdgeCode *edCd=new getEdgeCode();
+	bool hasEdge=false;
+	for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
+	    ++CI){
+	  if(*CI==ed && CI->getWeight()==N->weight){
+	    hasEdge=true;
+	    break;
+	  }
 	}
-      }
-      if(hasEdge){
-	char str[100];
-	if(instr[ed]!=NULL && instr[ed]->getCond()==1){
-	  instr[ed]->setCond(4);
+	if(hasEdge){
+	  char str[100];
+	  if(instr[ed]!=NULL && instr[ed]->getCond()==1){
+	    instr[ed]->setCond(4);
+	  }
+	  else{
+	    edCd->setCond(5);
+	    edCd->setInc(edIncrements[ed]);
+	    instr[ed]=edCd;
+	  }
+	  
 	}
+	else if(g.getNumberOfOutgoingEdges(v)==1)
+	  ws.push_back(v);
 	else{
-	  edCd->setCond(5);
-	  edCd->setInc(edIncrements[ed]);
+	  edCd->setCond(6);
 	  instr[ed]=edCd;
 	}
-	
-      }
-      else if(g.getSuccNodes(v).size()==1)
-	ws.push_back(v);
-      else{
-	edCd->setCond(6);
-	instr[ed]=edCd;
       }
     }
   }
-
   ///// Register increment code
   for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE; ++CI){
     getEdgeCode *edCd=new getEdgeCode();
@@ -310,6 +366,7 @@ static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *> &instr,
 //If a->b is a backedge
 //then incoming dummy edge is root->b
 //and outgoing dummy edge is a->exit
+//changed
 void addDummyEdges(vector<Edge > &stDummy, 
 		   vector<Edge > &exDummy, 
 		   Graph &g, vector<Edge> &be){
@@ -320,21 +377,15 @@ void addDummyEdges(vector<Edge > &stDummy,
     g.removeEdge(ed);
 
     if(!(*second==*(g.getRoot()))){
-      Edge *st=new Edge(g.getRoot(), second); 
-      
-      //check if stDummy doesn't have it already
-      if(find(stDummy.begin(), stDummy.end(), *st) == stDummy.end())
-	stDummy.push_back(*st);
+      Edge *st=new Edge(g.getRoot(), second, ed.getWeight(), ed.getRandId());
+      stDummy.push_back(*st);
       g.addEdgeForce(*st);
     }
 
     if(!(*first==*(g.getExit()))){
-      Edge *ex=new Edge(first, g.getExit());
-      
-      if (find(exDummy.begin(), exDummy.end(), *ex) == exDummy.end()) {
-	exDummy.push_back(*ex);
-	g.addEdgeForce(*ex);
-      }
+      Edge *ex=new Edge(first, g.getExit(), ed.getWeight(), ed.getRandId());
+      exDummy.push_back(*ex);
+      g.addEdgeForce(*ex);
     }
   }
 }
@@ -344,34 +395,73 @@ void printEdge(Edge ed){
   cerr<<((ed.getFirst())->getElement())
     ->getName()<<"->"<<((ed.getSecond())
 			  ->getElement())->getName()<<
-    ":"<<ed.getWeight()<<"\n";
+    ":"<<ed.getWeight()<<" rndId::"<<ed.getRandId()<<"\n";
 }
 
 //Move the incoming dummy edge code and outgoing dummy
 //edge code over to the corresponding back edge
-static void moveDummyCode(const vector<Edge> &stDummy, 
-                          const vector<Edge> &exDummy, 
-                          const vector<Edge> &be,  
-                          map<Edge, getEdgeCode *> &insertions){
-  typedef vector<Edge >::const_iterator vec_iter;
+static void moveDummyCode(vector<Edge> &stDummy, 
+                          vector<Edge> &exDummy, 
+                          vector<Edge> &be,  
+                          map<Edge, getEdgeCode *, EdgeCompare> &insertions, 
+			  Graph &g){
+  typedef vector<Edge >::iterator vec_iter;
   
-  DEBUG( //print all back, st and ex dummy
-        cerr<<"BackEdges---------------\n";
-        for(vec_iter VI=be.begin(); VI!=be.end(); ++VI)
-        printEdge(*VI);
-        cerr<<"StEdges---------------\n";
-        for(vec_iter VI=stDummy.begin(); VI!=stDummy.end(); ++VI)
-        printEdge(*VI);
-        cerr<<"ExitEdges---------------\n";
-        for(vec_iter VI=exDummy.begin(); VI!=exDummy.end(); ++VI)
-        printEdge(*VI);
-        cerr<<"------end all edges\n");
-
+  map<Edge,getEdgeCode *, EdgeCompare> temp;
+  //iterate over edges with code
   std::vector<Edge> toErase;
-  for(map<Edge,getEdgeCode *>::iterator MI=insertions.begin(), 
+  for(map<Edge,getEdgeCode *, EdgeCompare>::iterator MI=insertions.begin(), 
 	ME=insertions.end(); MI!=ME; ++MI){
     Edge ed=MI->first;
     getEdgeCode *edCd=MI->second;
+
+    ///---new code
+    //iterate over be, and check if its starts and end vertices hv code
+    for(vector<Edge>::iterator BEI=be.begin(), BEE=be.end(); BEI!=BEE; ++BEI){
+      if(ed.getRandId()==BEI->getRandId()){
+	
+	//cerr<<"Looking at edge--------\n";
+	//printEdge(ed);
+	
+	if(temp[*BEI]==0)
+	  temp[*BEI]=new getEdgeCode();
+	
+	//so ed is either in st, or ex!
+	if(ed.getFirst()==g.getRoot()){
+	  //so its in stDummy
+	  temp[*BEI]->setCdIn(edCd);
+	  toErase.push_back(ed);
+	}
+	else if(ed.getSecond()==g.getExit()){
+	  //so its in exDummy
+	  toErase.push_back(ed);
+	  temp[*BEI]->setCdOut(edCd);
+	}
+	else{
+	  assert(false && "Not found in either start or end! Rand failed?");
+	}
+      }
+    }
+  }
+  
+  for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme; 
+      ++vmi){
+    insertions.erase(*vmi);
+    //cerr<<"Erasing from insertion\n";
+    //printEdge(*vmi);
+    g.removeEdgeWithWt(*vmi);
+  }
+  
+  for(map<Edge,getEdgeCode *, EdgeCompare>::iterator MI=temp.begin(), 
+      ME=temp.end(); MI!=ME; ++MI){
+    insertions[MI->first]=MI->second;
+    //cerr<<"inserting into insertion-----\n";
+    //printEdge(MI->first);
+  }
+  //cerr<<"----\n";
+  
+  /*
+    ///---new code end
     bool dummyHasIt=false;
 
     DEBUG(cerr<<"Current edge considered---\n";
@@ -381,8 +471,10 @@ static void moveDummyCode(const vector<Edge> &stDummy,
     for(vec_iter VI=stDummy.begin(), VE=stDummy.end(); VI!=VE && !dummyHasIt; 
 	++VI){
       if(*VI==ed){
-	DEBUG(cerr<<"Edge matched with stDummy\n");
-
+	//#ifdef DEBUG_PATH_PROFILES
+	cerr<<"Edge matched with stDummy\n";
+	printEdge(ed);
+	//#endif
 	dummyHasIt=true;
 	bool dummyInBe=false;
 	//dummy edge with code
@@ -392,17 +484,24 @@ static void moveDummyCode(const vector<Edge> &stDummy,
 	  Node *dm=ed.getSecond();
 	  if(*dm==*st){
 	    //so this is the back edge to use
-	    DEBUG(cerr<<"Moving to backedge\n";
-                  printEdge(backEdge));
-
+	    //#ifdef DEBUG_PATH_PROFILES
+	    cerr<<"Moving to backedge\n";
+	    printEdge(backEdge);
+	    //#endif
 	    getEdgeCode *ged=new getEdgeCode();
 	    ged->setCdIn(edCd);
-	    toErase.push_back(ed);
+	    toErase.push_back(ed);//MI);//ed);
 	    insertions[backEdge]=ged;
 	    dummyInBe=true;
 	  }
 	}
 	assert(dummyInBe);
+	//modf
+	//new
+	//vec_iter VII=VI;
+	stDummy.erase(VI);
+	break;
+	//end new
       }
     }
     if(!dummyHasIt){
@@ -412,7 +511,10 @@ static void moveDummyCode(const vector<Edge> &stDummy,
 	  ++VI){
 	if(*VI==ed){
 	  inExDummy=true;
-	  DEBUG(cerr<<"Edge matched with exDummy\n");
+
+	  //#ifdef DEBUG_PATH_PROFILES
+	  cerr<<"Edge matched with exDummy\n";
+	  //#endif
 	  bool dummyInBe2=false;
 	  //dummy edge with code
 	  for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe2; 
@@ -422,30 +524,45 @@ static void moveDummyCode(const vector<Edge> &stDummy,
 	    Node *dm=ed.getFirst();
 	    if(*dm==*st){
 	      //so this is the back edge to use
+	      cerr<<"Moving to backedge\n";
+	      printEdge(backEdge);
 	      getEdgeCode *ged;
 	      if(insertions[backEdge]==NULL)
 		ged=new getEdgeCode();
 	      else
 		ged=insertions[backEdge];
-	      toErase.push_back(ed);
+	      toErase.push_back(ed);//MI);//ed);
 	      ged->setCdOut(edCd);
 	      insertions[backEdge]=ged;
 	      dummyInBe2=true;
 	    }
 	  }
 	  assert(dummyInBe2);
+	  //modf
+	  //vec_iter VII=VI;
+	  exDummy.erase(VI);
+	  break;
+	  //end
 	}
       }
     }
   }
 
-  DEBUG(cerr<<"size of deletions: "<<toErase.size()<<"\n");
+  */
+#ifdef DEBUG_PATH_PROFILES
+  cerr<<"size of deletions: "<<toErase.size()<<"\n";
+#endif
+  
+  /*
+  for(vector<map<Edge, getEdgeCode *>::iterator>::iterator 
+	vmi=toErase.begin(), vme=toErase.end(); vmi!=vme; ++vmi)
 
-  for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme; 
-      ++vmi)
     insertions.erase(*vmi);
+  */
+#ifdef DEBUG_PATH_PROFILES
+  cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n";
+#endif
 
-  DEBUG(cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n");
 }
 
 //Do graph processing: to determine minimal edge increments, 
@@ -456,7 +573,11 @@ void processGraph(Graph &g,
 		  Instruction *countInst, 
 		  vector<Edge >& be, 
 		  vector<Edge >& stDummy, 
-		  vector<Edge >& exDummy){
+		  vector<Edge >& exDummy, 
+		  int numPaths){
+
+  static int MethNo=0;
+  MethNo++;
   //Given a graph: with exit->root edge, do the following in seq:
   //1. get back edges
   //2. insert dummy edges and remove back edges
@@ -502,8 +623,10 @@ void processGraph(Graph &g,
   DEBUG(printGraph(g2));
 
   Graph *t=g2.getMaxSpanningTree();
-  DEBUG(printGraph(*t));
-
+  //#ifdef DEBUG_PATH_PROFILES
+  //cerr<<"Original maxspanning tree\n";
+  //printGraph(*t);
+  //#endif
   //now edges of tree t have weights reversed
   //(negative) because the algorithm used
   //to find max spanning tree is 
@@ -527,9 +650,11 @@ void processGraph(Graph &g,
   //the edge directions of corresponding edges in the directed graph
   removeTreeEdges(g, *t);
 
-  DEBUG(cerr<<"Spanning tree---------\n";
-        printGraph(*t);
-        cerr<<"-------end spanning tree\n");
+#ifdef DEBUG_PATH_PROFILES
+  cerr<<"Final Spanning tree---------\n";
+  printGraph(*t);
+  cerr<<"-------end spanning tree\n";
+#endif
 
   //now remove the exit->root node
   //and re-add it with weight 0
@@ -551,14 +676,18 @@ void processGraph(Graph &g,
   //and assign them some values such that 
   //if we consider just this subset, it still represents
   //the path sum along any path in the graph
-  map<Edge, int> increment=getEdgeIncrements(g,*t);
-
-  DEBUG(//print edge increments for debugging
-        for(map<Edge, int>::iterator MI=increment.begin(), ME = increment.end();
-            MI != ME; ++MI) {
-          printEdge(MI->first);
-          cerr << "Increment for above:" << MI->second << "\n";
-        });
+
+  map<Edge, int, EdgeCompare> increment=getEdgeIncrements(g,*t);
+#ifdef DEBUG_PATH_PROFILES
+  //print edge increments for debugging
+  
+  for(map<Edge, int, EdgeCompare>::iterator M_I=increment.begin(), M_E=increment.end(); 
+      M_I!=M_E; ++M_I){
+    printEdge(M_I->first);
+    cerr<<"Increment for above:"<<M_I->second<<"\n";
+  }
+#endif
+
  
   //step 6: Get code insertions
   
@@ -569,40 +698,51 @@ void processGraph(Graph &g,
   vector<Edge> chords;
   getChords(chords, g, *t);
 
-  map<Edge, getEdgeCode *> codeInsertions;
+
+  //cerr<<"Graph before getCodeInsertion:\n";
+  //printGraph(g);
+  map<Edge, getEdgeCode *, EdgeCompare> codeInsertions;
   getCodeInsertions(g, codeInsertions, chords,increment);
   
-  DEBUG (//print edges with code for debugging
-         cerr<<"Code inserted in following---------------\n";
-         for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(), 
-               cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
-           printEdge(cd_i->first);
-           cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
-         }
-         cerr<<"-----end insertions\n");
+#ifdef DEBUG_PATH_PROFILES
+  //print edges with code for debugging
+  cerr<<"Code inserted in following---------------\n";
+  for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(), 
+	cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
+    printEdge(cd_i->first);
+    cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
+  }
+  cerr<<"-----end insertions\n";
+#endif
 
   //step 7: move code on dummy edges over to the back edges
 
   //Move the incoming dummy edge code and outgoing dummy
   //edge code over to the corresponding back edge
-  moveDummyCode(stDummy, exDummy, be, codeInsertions);
-  
-  DEBUG(//debugging info
-        cerr<<"After moving dummy code\n";
-        for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(), 
-              cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){
-          printEdge(cd_i->first);
-          cerr<<cd_i->second->getCond()<<":"
-              <<cd_i->second->getInc()<<"\n";
-        }
-        cerr<<"Dummy end------------\n");
+
+  moveDummyCode(stDummy, exDummy, be, codeInsertions, g);
+  //cerr<<"After dummy removals\n";
+  //printGraph(g);
+
+#ifdef DEBUG_PATH_PROFILES
+  //debugging info
+  cerr<<"After moving dummy code\n";
+  for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(), 
+	cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){
+    printEdge(cd_i->first);
+    cerr<<cd_i->second->getCond()<<":"
+	<<cd_i->second->getInc()<<"\n";
+  }
+  cerr<<"Dummy end------------\n";
+#endif
+
 
   //see what it looks like...
   //now insert code along edges which have codes on them
   for(map<Edge, getEdgeCode *>::iterator MI=codeInsertions.begin(), 
 	ME=codeInsertions.end(); MI!=ME; ++MI){
     Edge ed=MI->first;
-    insertBB(ed, MI->second, rInst, countInst);
+    insertBB(ed, MI->second, rInst, countInst, numPaths, MethNo);
   } 
 }
 
@@ -610,18 +750,230 @@ void processGraph(Graph &g,
 
 //print the graph (for debugging)
 void printGraph(Graph &g){
-  list<Node *> lt=g.getAllNodes();
+  vector<Node *> lt=g.getAllNodes();
   cerr<<"Graph---------------------\n";
-  for(list<Node *>::iterator LI=lt.begin(); 
+  for(vector<Node *>::iterator LI=lt.begin(); 
       LI!=lt.end(); ++LI){
     cerr<<((*LI)->getElement())->getName()<<"->";
     Graph::nodeList nl=g.getNodeList(*LI);
     for(Graph::nodeList::iterator NI=nl.begin(); 
 	NI!=nl.end(); ++NI){
       cerr<<":"<<"("<<(NI->element->getElement())
-	->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")";
+	->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<","
+	  <<NI->randId<<")";
     }
     cerr<<"\n";
   }
   cerr<<"--------------------Graph\n";
 }
+
+
+/*
+////////// Getting back BBs from path number
+
+#include "llvm/Constants.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/iMemory.h"
+#include "llvm/iTerminators.h"
+#include "llvm/iOther.h"
+#include "llvm/iOperators.h"
+
+#include "llvm/Support/CFG.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Pass.h"
+
+void getPathFrmNode(Node *n, vector<BasicBlock*> &vBB, int pathNo, Graph g, 
+		    vector<Edge> &stDummy, vector<Edge> &exDummy, vector<Edge> &be,
+		    double strand){
+  Graph::nodeList nlist=g.getNodeList(n);
+  int maxCount=-9999999;
+  bool isStart=false;
+
+  if(*n==*g.getRoot())//its root: so first node of path
+    isStart=true;
+
+  double edgeRnd=0;
+  Node *nextRoot=n;
+  for(Graph::nodeList::iterator NLI=nlist.begin(), NLE=nlist.end(); NLI!=NLE;
+      ++NLI){
+    //cerr<<"Saw:"<<NLI->weight<<endl;
+    if(NLI->weight>maxCount && NLI->weight<=pathNo){
+      maxCount=NLI->weight;
+      nextRoot=NLI->element;
+      edgeRnd=NLI->randId;
+      if(isStart)
+	strand=NLI->randId;
+    }
+  }
+  //cerr<<"Max:"<<maxCount<<endl;
+
+  if(!isStart)
+    assert(strand!=-1 && "strand not assigned!"); 
+
+  assert(!(*nextRoot==*n && pathNo>0) && "No more BBs to go");
+  assert(!(*nextRoot==*g.getExit() && pathNo-maxCount!=0) && "Reached exit");
+
+  vBB.push_back(n->getElement());
+
+  if(pathNo-maxCount==0 && *nextRoot==*g.getExit()){
+
+    //look for strnd and edgeRnd now:
+    bool has1=false, has2=false;
+    //check if exit has it
+    for(vector<Edge>::iterator VI=exDummy.begin(), VE=exDummy.end(); VI!=VE; 
+	++VI){
+      if(VI->getRandId()==edgeRnd){
+	has2=true;
+	//cerr<<"has2: looking at"<<std::endl;
+	//printEdge(*VI);
+	break;
+      }
+    }
+
+    //check if start has it
+    for(vector<Edge>::iterator VI=stDummy.begin(), VE=stDummy.end(); VI!=VE; 
+	++VI){
+      if(VI->getRandId()==strand){
+	//cerr<<"has1: looking at"<<std::endl;
+        //printEdge(*VI);
+	has1=true;
+	break;
+      }
+    }
+
+    if(has1){
+      //find backedge with endpoint vBB[1]
+      for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
+	assert(vBB.size()>0 && "vector too small");
+	if( VI->getSecond()->getElement() == vBB[1] ){
+	  vBB[0]=VI->getFirst()->getElement();
+	  break;
+	}
+      }
+    }
+
+    if(has2){
+      //find backedge with startpoint vBB[vBB.size()-1]
+      for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
+	assert(vBB.size()>0 && "vector too small");
+	if( VI->getFirst()->getElement() == vBB[vBB.size()-1] ){
+	  //if(vBB[0]==VI->getFirst()->getElement())
+	  //vBB.erase(vBB.begin()+vBB.size()-1);
+	  //else
+	  vBB.push_back(VI->getSecond()->getElement());
+	  break;
+	}
+      }
+    }
+    else 
+      vBB.push_back(nextRoot->getElement());
+   
+    return;
+  }
+
+  assert(pathNo-maxCount>=0);
+
+  return getPathFrmNode(nextRoot, vBB, pathNo-maxCount, g, stDummy, 
+			exDummy, be, strand);
+}
+
+
+static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){
+  for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
+    if(((*si)->getElement())==BB){
+      return *si;
+    }
+  }
+  return NULL;
+}
+
+void getBBtrace(vector<BasicBlock *> &vBB, int pathNo, Function *M){
+
+  //step 1: create graph
+  //Transform the cfg s.t. we have just one exit node
+  
+  std::vector<Node *> nodes;
+  std::vector<Edge> edges;
+  Node *tmp;
+  Node *exitNode=0, *startNode=0;
+  
+  BasicBlock *ExitNode = 0;
+  for (Function::iterator I = M->begin(), E = M->end(); I != E; ++I) {
+    BasicBlock *BB = *I;
+    if (isa<ReturnInst>(BB->getTerminator())) {
+      ExitNode = BB;
+      break;
+    }
+  }
+  
+  assert(ExitNode!=0 && "exitnode not found");
+
+  //iterating over BBs and making graph 
+  //The nodes must be uniquesly identified:
+  //That is, no two nodes must hav same BB*
+  
+  //First enter just nodes: later enter edges
+  for(Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
+    Node *nd=new Node(*BB);
+    nodes.push_back(nd); 
+    if(*BB==ExitNode)
+      exitNode=nd;
+    if(*BB==M->front())
+      startNode=nd;
+  }
+  
+  assert(exitNode!=0 && startNode!=0 && "Start or exit not found!");
+ 
+  for (Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
+    Node *nd=findBB(nodes, *BB);
+    assert(nd && "No node for this edge!");
+
+    for(BasicBlock::succ_iterator s=succ_begin(*BB), se=succ_end(*BB); 
+	s!=se; ++s){
+      Node *nd2=findBB(nodes,*s);
+      assert(nd2 && "No node for this edge!");
+      Edge ed(nd,nd2,0);
+      edges.push_back(ed);
+    }
+  }
+  
+  static bool printed=false;
+  Graph g(nodes,edges, startNode, exitNode);
+
+  //if(!printed)
+  //printGraph(g);
+
+  if (M->getBasicBlocks().size() <= 1) return; //uninstrumented 
+
+  //step 2: getBackEdges
+  vector<Edge> be;
+  g.getBackEdges(be);
+
+  //cerr<<"BackEdges\n";
+  //for(vector<Edge>::iterator VI=be.begin(); VI!=be.end(); ++VI){
+    //printEdge(*VI);
+    //cerr<<"\n";
+  //}
+  //cerr<<"------\n";
+  //step 3: add dummy edges
+  vector<Edge> stDummy;
+  vector<Edge> exDummy;
+  addDummyEdges(stDummy, exDummy, g, be);
+
+  //cerr<<"After adding dummy edges\n";
+  //printGraph(g);
+
+  //step 4: value assgn to edges
+  int numPaths=valueAssignmentToEdges(g);
+  
+  //if(!printed){
+  //printGraph(g);
+  //printed=true;
+  //}
+
+  //step 5: now travel from root, select max(edge) < pathNo, 
+  //and go on until reach the exit
+  return getPathFrmNode(g.getRoot(), vBB, pathNo, g, stDummy, exDummy, be, -1);
+}
+
+*/
diff --git a/llvm/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxillary.cpp b/llvm/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxillary.cpp
index b2c5445c450..1eadcb6c6ad 100644
--- a/llvm/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxillary.cpp
+++ b/llvm/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxillary.cpp
@@ -6,12 +6,15 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "Graph.h"
+#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
+#include "llvm/Function.h"
+#include "llvm/Pass.h"
 #include "llvm/BasicBlock.h"
+#include "llvm/Transforms/Instrumentation/Graph.h"
 #include <algorithm>
 #include <iostream>
 
-using std::list;
+//using std::list;
 using std::map;
 using std::vector;
 using std::cerr;
@@ -25,13 +28,13 @@ static bool edgesEqual(Edge  ed1, Edge ed2){
 static void getChords(vector<Edge > &chords, Graph &g, Graph st){
   //make sure the spanning tree is directional
   //iterate over ALL the edges of the graph
-  list<Node *> allNodes=g.getAllNodes();
-  for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
+  vector<Node *> allNodes=g.getAllNodes();
+  for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
       ++NI){
     Graph::nodeList node_list=g.getNodeList(*NI);
     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
 	NLI!=NLE; ++NLI){
-      Edge f(*NI, NLI->element,NLI->weight);
+      Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
       if(!(st.hasEdgeAndWt(f)))//addnl
 	chords.push_back(f);
     }
@@ -46,8 +49,8 @@ static void getChords(vector<Edge > &chords, Graph &g, Graph st){
 //the tree so that now, all edge directions in the tree match
 //the edge directions of corresponding edges in the directed graph
 static void removeTreeEdges(Graph &g, Graph& t){
-  list<Node* > allNodes=t.getAllNodes();
-  for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
+  vector<Node* > allNodes=t.getAllNodes();
+  for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
       ++NI){
     Graph::nodeList nl=t.getNodeList(*NI);
     for(Graph::nodeList::iterator NLI=nl.begin(), NLE=nl.end();	NLI!=NLE;++NLI){
@@ -64,18 +67,40 @@ static void removeTreeEdges(Graph &g, Graph& t){
 //add up the edge values, we get a path number that uniquely
 //refers to the path we travelled
 int valueAssignmentToEdges(Graph& g){
-  list<Node *> revtop=g.reverseTopologicalSort();
+  vector<Node *> revtop=g.reverseTopologicalSort();
+  /*
+  std::cerr<<"-----------Reverse topological sort\n";
+  for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); RI!=RE; ++RI){
+    std::cerr<<(*RI)->getElement()->getName()<<":";
+  }
+  std::cerr<<"\n----------------------"<<std::endl;
+  */
   map<Node *,int > NumPaths;
-  for(list<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); RI!=RE; ++RI){
+  for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); RI!=RE; ++RI){
     if(g.isLeaf(*RI))
       NumPaths[*RI]=1;
     else{
       NumPaths[*RI]=0;
-      list<Node *> succ=g.getSuccNodes(*RI);
-      for(list<Node *>::iterator SI=succ.begin(), SE=succ.end(); SI!=SE; ++SI){
-	Edge ed(*RI,*SI,NumPaths[*RI]);
-	g.setWeight(ed);
-	NumPaths[*RI]+=NumPaths[*SI];
+      /////
+      Graph::nodeList &nlist=g.getNodeList(*RI);
+      //sort nodelist by increasing order of numpaths
+      
+      int sz=nlist.size();
+      for(int i=0;i<sz-1; i++){
+	int min=i;
+	for(int j=i+1; j<sz; j++)
+	  if(NumPaths[nlist[j].element]<NumPaths[nlist[min].element]) min=j;
+	
+	graphListElement tempEl=nlist[min];
+	nlist[min]=nlist[i];
+	nlist[i]=tempEl;
+      }
+      //sorted now!
+
+      for(Graph::nodeList::iterator GLI=nlist.begin(), GLE=nlist.end();
+	  GLI!=GLE; ++GLI){
+	GLI->weight=NumPaths[*RI];
+	NumPaths[*RI]+=NumPaths[GLI->element];
       }
     }
   }
@@ -108,19 +133,26 @@ static int inc_Dir(Edge e, Edge f){
   return -1;
 }
 
+
 //used for getting edge increments (read comments above in inc_Dir)
 //inc_DFS is a modification of DFS 
-static void inc_DFS(Graph& g,Graph& t,map<Edge, int>& Increment, 
+static void inc_DFS(Graph& g,Graph& t,map<Edge, int, EdgeCompare>& Increment, 
 	     int events, Node *v, Edge e){
   
-  list<Node *> allNodes=t.getAllNodes();
-  
-  for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
+  vector<Node *> allNodes=t.getAllNodes();
+
+
+  //cerr<<"Called for\n";
+  //if(!e.isNull())
+  //printEdge(e);
+
+
+  for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
       ++NI){
     Graph::nodeList node_list=t.getNodeList(*NI);
     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
 	NLI!= NLE; ++NLI){
-      Edge f(*NI, NLI->element,NLI->weight);
+      Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
       if(!edgesEqual(f,e) && *v==*(f.getSecond())){
 	int dir_count=inc_Dir(e,f);
 	int wt=1*f.getWeight();
@@ -129,15 +161,15 @@ static void inc_DFS(Graph& g,Graph& t,map<Edge, int>& Increment,
     }
   }
 
-  for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
+  for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
       ++NI){
     Graph::nodeList node_list=t.getNodeList(*NI);
     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
 	NLI!=NLE; ++NLI){
-      Edge f(*NI, NLI->element,NLI->weight);
+      Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
       if(!edgesEqual(f,e) && *v==*(f.getFirst())){
       	int dir_count=inc_Dir(e,f);
-	int wt=1*f.getWeight();
+	int wt=f.getWeight();
 	inc_DFS(g,t, Increment, dir_count*events+wt, 
 		f.getSecond(), f);
       }
@@ -145,16 +177,18 @@ static void inc_DFS(Graph& g,Graph& t,map<Edge, int>& Increment,
   }
 
   allNodes=g.getAllNodes();
-  for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
+  for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
       ++NI){
     Graph::nodeList node_list=g.getNodeList(*NI);
     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
 	NLI!=NLE; ++NLI){
-      Edge f(*NI, NLI->element,NLI->weight);
+      Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
       if(!(t.hasEdgeAndWt(f)) && (*v==*(f.getSecond()) || 
 				  *v==*(f.getFirst()))){
 	int dir_count=inc_Dir(e,f);
 	Increment[f]+=dir_count*events;
+	//cerr<<"assigned "<<Increment[f]<<" to"<<endl;
+	//printEdge(f);
       }
     }
   }
@@ -164,19 +198,19 @@ static void inc_DFS(Graph& g,Graph& t,map<Edge, int>& Increment,
 //and assign them some values such that 
 //if we consider just this subset, it still represents
 //the path sum along any path in the graph
-static map<Edge, int> getEdgeIncrements(Graph& g, Graph& t){
+static map<Edge, int, EdgeCompare> getEdgeIncrements(Graph& g, Graph& t){
   //get all edges in g-t
-  map<Edge, int> Increment;
+  map<Edge, int, EdgeCompare> Increment;
 
-  list<Node *> allNodes=g.getAllNodes();
+  vector<Node *> allNodes=g.getAllNodes();
  
-  for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
+  for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
       ++NI){
     Graph::nodeList node_list=g.getNodeList(*NI);
     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
 	NLI!=NLE; ++NLI){
-      Edge ed(*NI, NLI->element,NLI->weight);
-      if(!(t.hasEdge(ed))){
+      Edge ed(*NI, NLI->element,NLI->weight,NLI->randId);
+      if(!(t.hasEdgeAndWt(ed))){
 	Increment[ed]=0;;
       }
     }
@@ -185,14 +219,13 @@ static map<Edge, int> getEdgeIncrements(Graph& g, Graph& t){
   Edge *ed=new Edge();
   inc_DFS(g,t,Increment, 0, g.getRoot(), *ed);
 
-
-  for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
+  for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
       ++NI){
     Graph::nodeList node_list=g.getNodeList(*NI);
     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
 	NLI!=NLE; ++NLI){
-      Edge ed(*NI, NLI->element,NLI->weight);
-      if(!(t.hasEdge(ed))){
+      Edge ed(*NI, NLI->element,NLI->weight, NLI->randId);
+      if(!(t.hasEdgeAndWt(ed))){
 	int wt=ed.getWeight();
 	Increment[ed]+=wt;
       }
@@ -202,13 +235,20 @@ static map<Edge, int> getEdgeIncrements(Graph& g, Graph& t){
   return Increment;
 }
 
+//push it up: TODO
+const graphListElement *findNodeInList(const Graph::nodeList &NL,
+					      Node *N);
+
+graphListElement *findNodeInList(Graph::nodeList &NL, Node *N);
+//end TODO
+
 //Based on edgeIncrements (above), now obtain
 //the kind of code to be inserted along an edge
 //The idea here is to minimize the computation
 //by inserting only the needed code
-static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *> &instr,
+static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *, EdgeCompare> &instr,
                               vector<Edge > &chords, 
-                              map<Edge,int> &edIncrements){
+                              map<Edge,int, EdgeCompare> &edIncrements){
 
   //Register initialization code
   vector<Node *> ws;
@@ -224,29 +264,34 @@ static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *> &instr,
       int edgeWt=nl->weight;
       Node *w=nl->element;
       //if chords has v->w
-      Edge ed(v,w);
-      
+      Edge ed(v,w, edgeWt, nl->randId);
+      //cerr<<"Assign:\n";
+      //printEdge(ed);
       bool hasEdge=false;
       for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
 	  CI!=CE && !hasEdge;++CI){
-	if(*CI==ed){
+	if(*CI==ed && CI->getWeight()==edgeWt){//modf
 	  hasEdge=true;
 	}
       }
-      if(hasEdge){
+
+      if(hasEdge){//so its a chord edge
 	getEdgeCode *edCd=new getEdgeCode();
 	edCd->setCond(1);
 	edCd->setInc(edIncrements[ed]);
 	instr[ed]=edCd;
+	//std::cerr<<"Case 1\n";
       }
-      else if((g.getPredNodes(w)).size()==1){
+      else if(g.getNumberOfIncomingEdges(w)==1){
 	ws.push_back(w);
+	//std::cerr<<"Added w\n";
       }
       else{
 	getEdgeCode *edCd=new getEdgeCode();
 	edCd->setCond(2);
 	edCd->setInc(0);
 	instr[ed]=edCd;
+	//std::cerr<<"Case 2\n";
       }
     }
   }
@@ -257,44 +302,55 @@ static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *> &instr,
   while(!ws.empty()) {
     Node *w=ws.back();
     ws.pop_back();
-    
-    //for each edge v->w
-    list<Node *> preds=g.getPredNodes(w);
-    for(list<Node *>::iterator pd=preds.begin(), pe=preds.end(); pd!=pe; ++pd){
-      Node *v=*pd;
-      //if chords has v->w
-    
-      Edge ed(v,w);
-      getEdgeCode *edCd=new getEdgeCode();
-      bool hasEdge=false;
-      for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
-	  ++CI){
-	if(*CI==ed){
-	  hasEdge=true;
-	  break;
+
+
+    ///////
+    //vector<Node *> lt;
+    vector<Node *> lllt=g.getAllNodes();
+    for(vector<Node *>::iterator EII=lllt.begin(); EII!=lllt.end() ;++EII){
+      Node *lnode=*EII;
+      Graph::nodeList &nl = g.getNodeList(lnode);
+      //cerr<<"Size:"<<lllt.size()<<"\n";
+      //cerr<<lnode->getElement()->getName()<<"\n";
+      graphListElement *N = findNodeInList(nl, w);
+      if (N){// lt.push_back(lnode);
+	
+	//Node *v=*pd;
+	//Node *v=N->element;
+	Node *v=lnode;
+	//if chords has v->w
+	
+	Edge ed(v,w, N->weight, N->randId);
+	getEdgeCode *edCd=new getEdgeCode();
+	bool hasEdge=false;
+	for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
+	    ++CI){
+	  if(*CI==ed && CI->getWeight()==N->weight){
+	    hasEdge=true;
+	    break;
+	  }
 	}
-      }
-      if(hasEdge){
-	char str[100];
-	if(instr[ed]!=NULL && instr[ed]->getCond()==1){
-	  instr[ed]->setCond(4);
+	if(hasEdge){
+	  char str[100];
+	  if(instr[ed]!=NULL && instr[ed]->getCond()==1){
+	    instr[ed]->setCond(4);
+	  }
+	  else{
+	    edCd->setCond(5);
+	    edCd->setInc(edIncrements[ed]);
+	    instr[ed]=edCd;
+	  }
+	  
 	}
+	else if(g.getNumberOfOutgoingEdges(v)==1)
+	  ws.push_back(v);
 	else{
-	  edCd->setCond(5);
-	  edCd->setInc(edIncrements[ed]);
+	  edCd->setCond(6);
 	  instr[ed]=edCd;
 	}
-	
-      }
-      else if(g.getSuccNodes(v).size()==1)
-	ws.push_back(v);
-      else{
-	edCd->setCond(6);
-	instr[ed]=edCd;
       }
     }
   }
-
   ///// Register increment code
   for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE; ++CI){
     getEdgeCode *edCd=new getEdgeCode();
@@ -310,6 +366,7 @@ static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *> &instr,
 //If a->b is a backedge
 //then incoming dummy edge is root->b
 //and outgoing dummy edge is a->exit
+//changed
 void addDummyEdges(vector<Edge > &stDummy, 
 		   vector<Edge > &exDummy, 
 		   Graph &g, vector<Edge> &be){
@@ -320,21 +377,15 @@ void addDummyEdges(vector<Edge > &stDummy,
     g.removeEdge(ed);
 
     if(!(*second==*(g.getRoot()))){
-      Edge *st=new Edge(g.getRoot(), second); 
-      
-      //check if stDummy doesn't have it already
-      if(find(stDummy.begin(), stDummy.end(), *st) == stDummy.end())
-	stDummy.push_back(*st);
+      Edge *st=new Edge(g.getRoot(), second, ed.getWeight(), ed.getRandId());
+      stDummy.push_back(*st);
       g.addEdgeForce(*st);
     }
 
     if(!(*first==*(g.getExit()))){
-      Edge *ex=new Edge(first, g.getExit());
-      
-      if (find(exDummy.begin(), exDummy.end(), *ex) == exDummy.end()) {
-	exDummy.push_back(*ex);
-	g.addEdgeForce(*ex);
-      }
+      Edge *ex=new Edge(first, g.getExit(), ed.getWeight(), ed.getRandId());
+      exDummy.push_back(*ex);
+      g.addEdgeForce(*ex);
     }
   }
 }
@@ -344,34 +395,73 @@ void printEdge(Edge ed){
   cerr<<((ed.getFirst())->getElement())
     ->getName()<<"->"<<((ed.getSecond())
 			  ->getElement())->getName()<<
-    ":"<<ed.getWeight()<<"\n";
+    ":"<<ed.getWeight()<<" rndId::"<<ed.getRandId()<<"\n";
 }
 
 //Move the incoming dummy edge code and outgoing dummy
 //edge code over to the corresponding back edge
-static void moveDummyCode(const vector<Edge> &stDummy, 
-                          const vector<Edge> &exDummy, 
-                          const vector<Edge> &be,  
-                          map<Edge, getEdgeCode *> &insertions){
-  typedef vector<Edge >::const_iterator vec_iter;
+static void moveDummyCode(vector<Edge> &stDummy, 
+                          vector<Edge> &exDummy, 
+                          vector<Edge> &be,  
+                          map<Edge, getEdgeCode *, EdgeCompare> &insertions, 
+			  Graph &g){
+  typedef vector<Edge >::iterator vec_iter;
   
-  DEBUG( //print all back, st and ex dummy
-        cerr<<"BackEdges---------------\n";
-        for(vec_iter VI=be.begin(); VI!=be.end(); ++VI)
-        printEdge(*VI);
-        cerr<<"StEdges---------------\n";
-        for(vec_iter VI=stDummy.begin(); VI!=stDummy.end(); ++VI)
-        printEdge(*VI);
-        cerr<<"ExitEdges---------------\n";
-        for(vec_iter VI=exDummy.begin(); VI!=exDummy.end(); ++VI)
-        printEdge(*VI);
-        cerr<<"------end all edges\n");
-
+  map<Edge,getEdgeCode *, EdgeCompare> temp;
+  //iterate over edges with code
   std::vector<Edge> toErase;
-  for(map<Edge,getEdgeCode *>::iterator MI=insertions.begin(), 
+  for(map<Edge,getEdgeCode *, EdgeCompare>::iterator MI=insertions.begin(), 
 	ME=insertions.end(); MI!=ME; ++MI){
     Edge ed=MI->first;
     getEdgeCode *edCd=MI->second;
+
+    ///---new code
+    //iterate over be, and check if its starts and end vertices hv code
+    for(vector<Edge>::iterator BEI=be.begin(), BEE=be.end(); BEI!=BEE; ++BEI){
+      if(ed.getRandId()==BEI->getRandId()){
+	
+	//cerr<<"Looking at edge--------\n";
+	//printEdge(ed);
+	
+	if(temp[*BEI]==0)
+	  temp[*BEI]=new getEdgeCode();
+	
+	//so ed is either in st, or ex!
+	if(ed.getFirst()==g.getRoot()){
+	  //so its in stDummy
+	  temp[*BEI]->setCdIn(edCd);
+	  toErase.push_back(ed);
+	}
+	else if(ed.getSecond()==g.getExit()){
+	  //so its in exDummy
+	  toErase.push_back(ed);
+	  temp[*BEI]->setCdOut(edCd);
+	}
+	else{
+	  assert(false && "Not found in either start or end! Rand failed?");
+	}
+      }
+    }
+  }
+  
+  for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme; 
+      ++vmi){
+    insertions.erase(*vmi);
+    //cerr<<"Erasing from insertion\n";
+    //printEdge(*vmi);
+    g.removeEdgeWithWt(*vmi);
+  }
+  
+  for(map<Edge,getEdgeCode *, EdgeCompare>::iterator MI=temp.begin(), 
+      ME=temp.end(); MI!=ME; ++MI){
+    insertions[MI->first]=MI->second;
+    //cerr<<"inserting into insertion-----\n";
+    //printEdge(MI->first);
+  }
+  //cerr<<"----\n";
+  
+  /*
+    ///---new code end
     bool dummyHasIt=false;
 
     DEBUG(cerr<<"Current edge considered---\n";
@@ -381,8 +471,10 @@ static void moveDummyCode(const vector<Edge> &stDummy,
     for(vec_iter VI=stDummy.begin(), VE=stDummy.end(); VI!=VE && !dummyHasIt; 
 	++VI){
       if(*VI==ed){
-	DEBUG(cerr<<"Edge matched with stDummy\n");
-
+	//#ifdef DEBUG_PATH_PROFILES
+	cerr<<"Edge matched with stDummy\n";
+	printEdge(ed);
+	//#endif
 	dummyHasIt=true;
 	bool dummyInBe=false;
 	//dummy edge with code
@@ -392,17 +484,24 @@ static void moveDummyCode(const vector<Edge> &stDummy,
 	  Node *dm=ed.getSecond();
 	  if(*dm==*st){
 	    //so this is the back edge to use
-	    DEBUG(cerr<<"Moving to backedge\n";
-                  printEdge(backEdge));
-
+	    //#ifdef DEBUG_PATH_PROFILES
+	    cerr<<"Moving to backedge\n";
+	    printEdge(backEdge);
+	    //#endif
 	    getEdgeCode *ged=new getEdgeCode();
 	    ged->setCdIn(edCd);
-	    toErase.push_back(ed);
+	    toErase.push_back(ed);//MI);//ed);
 	    insertions[backEdge]=ged;
 	    dummyInBe=true;
 	  }
 	}
 	assert(dummyInBe);
+	//modf
+	//new
+	//vec_iter VII=VI;
+	stDummy.erase(VI);
+	break;
+	//end new
       }
     }
     if(!dummyHasIt){
@@ -412,7 +511,10 @@ static void moveDummyCode(const vector<Edge> &stDummy,
 	  ++VI){
 	if(*VI==ed){
 	  inExDummy=true;
-	  DEBUG(cerr<<"Edge matched with exDummy\n");
+
+	  //#ifdef DEBUG_PATH_PROFILES
+	  cerr<<"Edge matched with exDummy\n";
+	  //#endif
 	  bool dummyInBe2=false;
 	  //dummy edge with code
 	  for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe2; 
@@ -422,30 +524,45 @@ static void moveDummyCode(const vector<Edge> &stDummy,
 	    Node *dm=ed.getFirst();
 	    if(*dm==*st){
 	      //so this is the back edge to use
+	      cerr<<"Moving to backedge\n";
+	      printEdge(backEdge);
 	      getEdgeCode *ged;
 	      if(insertions[backEdge]==NULL)
 		ged=new getEdgeCode();
 	      else
 		ged=insertions[backEdge];
-	      toErase.push_back(ed);
+	      toErase.push_back(ed);//MI);//ed);
 	      ged->setCdOut(edCd);
 	      insertions[backEdge]=ged;
 	      dummyInBe2=true;
 	    }
 	  }
 	  assert(dummyInBe2);
+	  //modf
+	  //vec_iter VII=VI;
+	  exDummy.erase(VI);
+	  break;
+	  //end
 	}
       }
     }
   }
 
-  DEBUG(cerr<<"size of deletions: "<<toErase.size()<<"\n");
+  */
+#ifdef DEBUG_PATH_PROFILES
+  cerr<<"size of deletions: "<<toErase.size()<<"\n";
+#endif
+  
+  /*
+  for(vector<map<Edge, getEdgeCode *>::iterator>::iterator 
+	vmi=toErase.begin(), vme=toErase.end(); vmi!=vme; ++vmi)
 
-  for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme; 
-      ++vmi)
     insertions.erase(*vmi);
+  */
+#ifdef DEBUG_PATH_PROFILES
+  cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n";
+#endif
 
-  DEBUG(cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n");
 }
 
 //Do graph processing: to determine minimal edge increments, 
@@ -456,7 +573,11 @@ void processGraph(Graph &g,
 		  Instruction *countInst, 
 		  vector<Edge >& be, 
 		  vector<Edge >& stDummy, 
-		  vector<Edge >& exDummy){
+		  vector<Edge >& exDummy, 
+		  int numPaths){
+
+  static int MethNo=0;
+  MethNo++;
   //Given a graph: with exit->root edge, do the following in seq:
   //1. get back edges
   //2. insert dummy edges and remove back edges
@@ -502,8 +623,10 @@ void processGraph(Graph &g,
   DEBUG(printGraph(g2));
 
   Graph *t=g2.getMaxSpanningTree();
-  DEBUG(printGraph(*t));
-
+  //#ifdef DEBUG_PATH_PROFILES
+  //cerr<<"Original maxspanning tree\n";
+  //printGraph(*t);
+  //#endif
   //now edges of tree t have weights reversed
   //(negative) because the algorithm used
   //to find max spanning tree is 
@@ -527,9 +650,11 @@ void processGraph(Graph &g,
   //the edge directions of corresponding edges in the directed graph
   removeTreeEdges(g, *t);
 
-  DEBUG(cerr<<"Spanning tree---------\n";
-        printGraph(*t);
-        cerr<<"-------end spanning tree\n");
+#ifdef DEBUG_PATH_PROFILES
+  cerr<<"Final Spanning tree---------\n";
+  printGraph(*t);
+  cerr<<"-------end spanning tree\n";
+#endif
 
   //now remove the exit->root node
   //and re-add it with weight 0
@@ -551,14 +676,18 @@ void processGraph(Graph &g,
   //and assign them some values such that 
   //if we consider just this subset, it still represents
   //the path sum along any path in the graph
-  map<Edge, int> increment=getEdgeIncrements(g,*t);
-
-  DEBUG(//print edge increments for debugging
-        for(map<Edge, int>::iterator MI=increment.begin(), ME = increment.end();
-            MI != ME; ++MI) {
-          printEdge(MI->first);
-          cerr << "Increment for above:" << MI->second << "\n";
-        });
+
+  map<Edge, int, EdgeCompare> increment=getEdgeIncrements(g,*t);
+#ifdef DEBUG_PATH_PROFILES
+  //print edge increments for debugging
+  
+  for(map<Edge, int, EdgeCompare>::iterator M_I=increment.begin(), M_E=increment.end(); 
+      M_I!=M_E; ++M_I){
+    printEdge(M_I->first);
+    cerr<<"Increment for above:"<<M_I->second<<"\n";
+  }
+#endif
+
  
   //step 6: Get code insertions
   
@@ -569,40 +698,51 @@ void processGraph(Graph &g,
   vector<Edge> chords;
   getChords(chords, g, *t);
 
-  map<Edge, getEdgeCode *> codeInsertions;
+
+  //cerr<<"Graph before getCodeInsertion:\n";
+  //printGraph(g);
+  map<Edge, getEdgeCode *, EdgeCompare> codeInsertions;
   getCodeInsertions(g, codeInsertions, chords,increment);
   
-  DEBUG (//print edges with code for debugging
-         cerr<<"Code inserted in following---------------\n";
-         for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(), 
-               cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
-           printEdge(cd_i->first);
-           cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
-         }
-         cerr<<"-----end insertions\n");
+#ifdef DEBUG_PATH_PROFILES
+  //print edges with code for debugging
+  cerr<<"Code inserted in following---------------\n";
+  for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(), 
+	cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
+    printEdge(cd_i->first);
+    cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
+  }
+  cerr<<"-----end insertions\n";
+#endif
 
   //step 7: move code on dummy edges over to the back edges
 
   //Move the incoming dummy edge code and outgoing dummy
   //edge code over to the corresponding back edge
-  moveDummyCode(stDummy, exDummy, be, codeInsertions);
-  
-  DEBUG(//debugging info
-        cerr<<"After moving dummy code\n";
-        for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(), 
-              cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){
-          printEdge(cd_i->first);
-          cerr<<cd_i->second->getCond()<<":"
-              <<cd_i->second->getInc()<<"\n";
-        }
-        cerr<<"Dummy end------------\n");
+
+  moveDummyCode(stDummy, exDummy, be, codeInsertions, g);
+  //cerr<<"After dummy removals\n";
+  //printGraph(g);
+
+#ifdef DEBUG_PATH_PROFILES
+  //debugging info
+  cerr<<"After moving dummy code\n";
+  for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(), 
+	cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){
+    printEdge(cd_i->first);
+    cerr<<cd_i->second->getCond()<<":"
+	<<cd_i->second->getInc()<<"\n";
+  }
+  cerr<<"Dummy end------------\n";
+#endif
+
 
   //see what it looks like...
   //now insert code along edges which have codes on them
   for(map<Edge, getEdgeCode *>::iterator MI=codeInsertions.begin(), 
 	ME=codeInsertions.end(); MI!=ME; ++MI){
     Edge ed=MI->first;
-    insertBB(ed, MI->second, rInst, countInst);
+    insertBB(ed, MI->second, rInst, countInst, numPaths, MethNo);
   } 
 }
 
@@ -610,18 +750,230 @@ void processGraph(Graph &g,
 
 //print the graph (for debugging)
 void printGraph(Graph &g){
-  list<Node *> lt=g.getAllNodes();
+  vector<Node *> lt=g.getAllNodes();
   cerr<<"Graph---------------------\n";
-  for(list<Node *>::iterator LI=lt.begin(); 
+  for(vector<Node *>::iterator LI=lt.begin(); 
       LI!=lt.end(); ++LI){
     cerr<<((*LI)->getElement())->getName()<<"->";
     Graph::nodeList nl=g.getNodeList(*LI);
     for(Graph::nodeList::iterator NI=nl.begin(); 
 	NI!=nl.end(); ++NI){
       cerr<<":"<<"("<<(NI->element->getElement())
-	->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")";
+	->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<","
+	  <<NI->randId<<")";
     }
     cerr<<"\n";
   }
   cerr<<"--------------------Graph\n";
 }
+
+
+/*
+////////// Getting back BBs from path number
+
+#include "llvm/Constants.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/iMemory.h"
+#include "llvm/iTerminators.h"
+#include "llvm/iOther.h"
+#include "llvm/iOperators.h"
+
+#include "llvm/Support/CFG.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Pass.h"
+
+void getPathFrmNode(Node *n, vector<BasicBlock*> &vBB, int pathNo, Graph g, 
+		    vector<Edge> &stDummy, vector<Edge> &exDummy, vector<Edge> &be,
+		    double strand){
+  Graph::nodeList nlist=g.getNodeList(n);
+  int maxCount=-9999999;
+  bool isStart=false;
+
+  if(*n==*g.getRoot())//its root: so first node of path
+    isStart=true;
+
+  double edgeRnd=0;
+  Node *nextRoot=n;
+  for(Graph::nodeList::iterator NLI=nlist.begin(), NLE=nlist.end(); NLI!=NLE;
+      ++NLI){
+    //cerr<<"Saw:"<<NLI->weight<<endl;
+    if(NLI->weight>maxCount && NLI->weight<=pathNo){
+      maxCount=NLI->weight;
+      nextRoot=NLI->element;
+      edgeRnd=NLI->randId;
+      if(isStart)
+	strand=NLI->randId;
+    }
+  }
+  //cerr<<"Max:"<<maxCount<<endl;
+
+  if(!isStart)
+    assert(strand!=-1 && "strand not assigned!"); 
+
+  assert(!(*nextRoot==*n && pathNo>0) && "No more BBs to go");
+  assert(!(*nextRoot==*g.getExit() && pathNo-maxCount!=0) && "Reached exit");
+
+  vBB.push_back(n->getElement());
+
+  if(pathNo-maxCount==0 && *nextRoot==*g.getExit()){
+
+    //look for strnd and edgeRnd now:
+    bool has1=false, has2=false;
+    //check if exit has it
+    for(vector<Edge>::iterator VI=exDummy.begin(), VE=exDummy.end(); VI!=VE; 
+	++VI){
+      if(VI->getRandId()==edgeRnd){
+	has2=true;
+	//cerr<<"has2: looking at"<<std::endl;
+	//printEdge(*VI);
+	break;
+      }
+    }
+
+    //check if start has it
+    for(vector<Edge>::iterator VI=stDummy.begin(), VE=stDummy.end(); VI!=VE; 
+	++VI){
+      if(VI->getRandId()==strand){
+	//cerr<<"has1: looking at"<<std::endl;
+        //printEdge(*VI);
+	has1=true;
+	break;
+      }
+    }
+
+    if(has1){
+      //find backedge with endpoint vBB[1]
+      for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
+	assert(vBB.size()>0 && "vector too small");
+	if( VI->getSecond()->getElement() == vBB[1] ){
+	  vBB[0]=VI->getFirst()->getElement();
+	  break;
+	}
+      }
+    }
+
+    if(has2){
+      //find backedge with startpoint vBB[vBB.size()-1]
+      for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
+	assert(vBB.size()>0 && "vector too small");
+	if( VI->getFirst()->getElement() == vBB[vBB.size()-1] ){
+	  //if(vBB[0]==VI->getFirst()->getElement())
+	  //vBB.erase(vBB.begin()+vBB.size()-1);
+	  //else
+	  vBB.push_back(VI->getSecond()->getElement());
+	  break;
+	}
+      }
+    }
+    else 
+      vBB.push_back(nextRoot->getElement());
+   
+    return;
+  }
+
+  assert(pathNo-maxCount>=0);
+
+  return getPathFrmNode(nextRoot, vBB, pathNo-maxCount, g, stDummy, 
+			exDummy, be, strand);
+}
+
+
+static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){
+  for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
+    if(((*si)->getElement())==BB){
+      return *si;
+    }
+  }
+  return NULL;
+}
+
+void getBBtrace(vector<BasicBlock *> &vBB, int pathNo, Function *M){
+
+  //step 1: create graph
+  //Transform the cfg s.t. we have just one exit node
+  
+  std::vector<Node *> nodes;
+  std::vector<Edge> edges;
+  Node *tmp;
+  Node *exitNode=0, *startNode=0;
+  
+  BasicBlock *ExitNode = 0;
+  for (Function::iterator I = M->begin(), E = M->end(); I != E; ++I) {
+    BasicBlock *BB = *I;
+    if (isa<ReturnInst>(BB->getTerminator())) {
+      ExitNode = BB;
+      break;
+    }
+  }
+  
+  assert(ExitNode!=0 && "exitnode not found");
+
+  //iterating over BBs and making graph 
+  //The nodes must be uniquesly identified:
+  //That is, no two nodes must hav same BB*
+  
+  //First enter just nodes: later enter edges
+  for(Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
+    Node *nd=new Node(*BB);
+    nodes.push_back(nd); 
+    if(*BB==ExitNode)
+      exitNode=nd;
+    if(*BB==M->front())
+      startNode=nd;
+  }
+  
+  assert(exitNode!=0 && startNode!=0 && "Start or exit not found!");
+ 
+  for (Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
+    Node *nd=findBB(nodes, *BB);
+    assert(nd && "No node for this edge!");
+
+    for(BasicBlock::succ_iterator s=succ_begin(*BB), se=succ_end(*BB); 
+	s!=se; ++s){
+      Node *nd2=findBB(nodes,*s);
+      assert(nd2 && "No node for this edge!");
+      Edge ed(nd,nd2,0);
+      edges.push_back(ed);
+    }
+  }
+  
+  static bool printed=false;
+  Graph g(nodes,edges, startNode, exitNode);
+
+  //if(!printed)
+  //printGraph(g);
+
+  if (M->getBasicBlocks().size() <= 1) return; //uninstrumented 
+
+  //step 2: getBackEdges
+  vector<Edge> be;
+  g.getBackEdges(be);
+
+  //cerr<<"BackEdges\n";
+  //for(vector<Edge>::iterator VI=be.begin(); VI!=be.end(); ++VI){
+    //printEdge(*VI);
+    //cerr<<"\n";
+  //}
+  //cerr<<"------\n";
+  //step 3: add dummy edges
+  vector<Edge> stDummy;
+  vector<Edge> exDummy;
+  addDummyEdges(stDummy, exDummy, g, be);
+
+  //cerr<<"After adding dummy edges\n";
+  //printGraph(g);
+
+  //step 4: value assgn to edges
+  int numPaths=valueAssignmentToEdges(g);
+  
+  //if(!printed){
+  //printGraph(g);
+  //printed=true;
+  //}
+
+  //step 5: now travel from root, select max(edge) < pathNo, 
+  //and go on until reach the exit
+  return getPathFrmNode(g.getRoot(), vBB, pathNo, g, stDummy, exDummy, be, -1);
+}
+
+*/
diff --git a/llvm/lib/Transforms/Instrumentation/ProfilePaths/ProfilePaths.cpp b/llvm/lib/Transforms/Instrumentation/ProfilePaths/ProfilePaths.cpp
index 42ef33cb0d5..8bd8a6beda3 100644
--- a/llvm/lib/Transforms/Instrumentation/ProfilePaths/ProfilePaths.cpp
+++ b/llvm/lib/Transforms/Instrumentation/ProfilePaths/ProfilePaths.cpp
@@ -21,7 +21,7 @@
 // of a function is identified through a unique number. the code insertion
 // is optimal in the sense that its inserted over a minimal set of edges. Also,
 // the algorithm makes sure than initialization, path increment and counter
-// update can be collapsed into minmimum number of edges.
+// update can be collapsed into minimum number of edges.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Instrumentation/ProfilePaths.h"
@@ -30,7 +30,9 @@
 #include "llvm/Constants.h"
 #include "llvm/DerivedTypes.h"
 #include "llvm/iMemory.h"
-#include "Graph.h"
+#include "llvm/Transforms/Instrumentation/Graph.h"
+#include <iostream>
+#include <fstream>
 
 using std::vector;
 
@@ -54,8 +56,8 @@ Pass *createProfilePathsPass() {
 }
 
 
-static Node *findBB(std::set<Node *> &st, BasicBlock *BB){
-  for(std::set<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
+static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){
+  for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
     if(((*si)->getElement())==BB){
       return *si;
     }
@@ -65,12 +67,15 @@ static Node *findBB(std::set<Node *> &st, BasicBlock *BB){
 
 //Per function pass for inserting counters and trigger code
 bool ProfilePaths::runOnFunction(Function &F){
+
+  static int mn = -1;
   // Transform the cfg s.t. we have just one exit node
   BasicBlock *ExitNode = getAnalysis<UnifyFunctionExitNodes>().getExitNode();  
-  
-  // iterating over BBs and making graph
-  std::set<Node *> nodes;
-  std::set<Edge> edges;
+
+  //iterating over BBs and making graph
+  std::vector<Node *> nodes;
+  std::vector<Edge> edges;
+
   Node *tmp;
   Node *exitNode, *startNode;
 
@@ -78,10 +83,17 @@ bool ProfilePaths::runOnFunction(Function &F){
   // That is, no two nodes must hav same BB*
   
   // First enter just nodes: later enter edges
+  //<<<<<<< ProfilePaths.cpp
+  //for (Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
+  //Node *nd=new Node(*BB);
+  //nodes.push_back(nd); 
+  //if(*BB==ExitNode)
+  //=======
   for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB) {
     Node *nd=new Node(BB);
-    nodes.insert(nd); 
+    nodes.push_back(nd); 
     if(&*BB == ExitNode)
+      //>>>>>>> 1.13
       exitNode=nd;
     if(&*BB==F.begin())
       startNode=nd;
@@ -91,38 +103,62 @@ bool ProfilePaths::runOnFunction(Function &F){
   for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB){
     Node *nd=findBB(nodes, BB);
     assert(nd && "No node for this edge!");
+
     for(BasicBlock::succ_iterator s=succ_begin(BB), se=succ_end(BB); 
 	s!=se; ++s){
+      //tempVec.push_back(*s);
+      //}
+
+    //sort(tempVec.begin(), tempVec.end(), BBSort());
+
+    //for(vector<BasicBlock *>::iterator s=tempVec.begin(), se=tempVec.end(); 
+      //s!=se; ++s){
       Node *nd2=findBB(nodes,*s);
       assert(nd2 && "No node for this edge!");
       Edge ed(nd,nd2,0);
-      edges.insert(ed);
+      edges.push_back(ed);
     }
   }
   
   Graph g(nodes,edges, startNode, exitNode);
 
-  DEBUG(printGraph(g));
+  //#ifdef DEBUG_PATH_PROFILES  
+  //std::cerr<<"Original graph\n";
+  //printGraph(g);
+  //#endif
 
   BasicBlock *fr=&F.front();
   
   // If only one BB, don't instrument
-  if (++F.begin() == F.end()) {    
+  if (++F.begin() == F.end()) {
+    mn++;
     // The graph is made acyclic: this is done
     // by removing back edges for now, and adding them later on
     vector<Edge> be;
     g.getBackEdges(be);
-    DEBUG(cerr << "Backedges:" << be.size() << "\n");
-
-    // Now we need to reflect the effect of back edges
-    // This is done by adding dummy edges
-    // If a->b is a back edge
-    // Then we add 2 back edges for it:
-    // 1. from root->b (in vector stDummy)
-    // and 2. from a->exit (in vector exDummy)
+
+    //std::cerr<<"BackEdges-------------\n";
+    //   for(vector<Edge>::iterator VI=be.begin(); VI!=be.end(); ++VI){
+    //printEdge(*VI);
+      //cerr<<"\n";
+    //}
+    //std::cerr<<"------\n";
+
+#ifdef DEBUG_PATH_PROFILES
+    cerr<<"Backedges:"<<be.size()<<endl;
+#endif
+    //Now we need to reflect the effect of back edges
+    //This is done by adding dummy edges
+    //If a->b is a back edge
+    //Then we add 2 back edges for it:
+    //1. from root->b (in vector stDummy)
+    //and 2. from a->exit (in vector exDummy)
     vector<Edge> stDummy;
     vector<Edge> exDummy;
     addDummyEdges(stDummy, exDummy, g, be);
+
+    //std::cerr<<"After adding dummy edges\n";
+    //printGraph(g);
     
     // Now, every edge in the graph is assigned a weight
     // This weight later adds on to assign path
@@ -131,13 +167,16 @@ bool ProfilePaths::runOnFunction(Function &F){
     // since no back edges in the graph now
     // numPaths is the number of acyclic paths in the graph
     int numPaths=valueAssignmentToEdges(g);
-    
-    // create instruction allocation r and count
-    // r is the variable that'll act like an accumulator
-    // all along the path, we just add edge values to r
-    // and at the end, r reflects the path number
-    // count is an array: count[x] would store
-    // the number of executions of path numbered x
+
+    //std::cerr<<"Numpaths="<<numPaths<<std::endl;
+    //printGraph(g);
+    //create instruction allocation r and count
+    //r is the variable that'll act like an accumulator
+    //all along the path, we just add edge values to r
+    //and at the end, r reflects the path number
+    //count is an array: count[x] would store
+    //the number of executions of path numbered x
+
     Instruction *rVar=new 
       AllocaInst(PointerType::get(Type::IntTy), 
 		 ConstantUInt::get(Type::UIntTy,1),"R");
@@ -150,12 +189,37 @@ bool ProfilePaths::runOnFunction(Function &F){
     // this includes initializing r and count
     insertInTopBB(&F.getEntryNode(),numPaths, rVar, countVar);
     
-    // now process the graph: get path numbers,
-    // get increments along different paths,
-    // and assign "increments" and "updates" (to r and count)
-    // "optimally". Finally, insert llvm code along various edges
-    processGraph(g, rVar, countVar, be, stDummy, exDummy);
+    //now process the graph: get path numbers,
+    //get increments along different paths,
+    //and assign "increments" and "updates" (to r and count)
+    //"optimally". Finally, insert llvm code along various edges
+    processGraph(g, rVar, countVar, be, stDummy, exDummy, numPaths);    
+    /*
+    //get the paths
+    static std::ofstream to("paths.sizes");
+    static std::ofstream bbs("paths.look");
+    assert(to && "Cannot open file\n");
+    assert(bbs && "Cannot open file\n");
+    for(int i=0;i<numPaths; ++i){
+    std::vector<BasicBlock *> vBB;
+    
+    getBBtrace(vBB, i, M);
+    //get total size of vector
+    int size=0;
+    bbs<<"Meth:"<<mn<<" Path:"<<i<<"\n-------------\n";
+    for(vector<BasicBlock *>::iterator VBI=vBB.begin(); VBI!=vBB.end();
+    ++VBI){
+    BasicBlock *BB=*VBI;
+    size+=BB->size();
+    if(BB==M->front())
+    size-=numPaths;
+    bbs<<BB->getName()<<"->";
+    }
+    bbs<<"\n--------------\n";
+    to<<"::::: "<<mn<<" "<<i<<" "<<size<<"\n";
+    }
+    */
   }
-
+  
   return true;  // Always modifies function
 }