path: root/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxillary.cpp

//===-- GrapAuxillary.cpp- Auxillary functions on graph ----------*- C++ -*--=//
//
//auxillary function associated with graph: they
//all operate on graph, and help in inserting
//instrumentation for trace generation
//
//===----------------------------------------------------------------------===//

#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::map;
using std::vector;
using std::cerr;

//check if 2 edges are equal (same endpoints and same weight)
static bool edgesEqual(Edge  ed1, Edge ed2){
  return ((ed1==ed2) && ed1.getWeight()==ed2.getWeight());
}

//Get the vector of edges that are to be instrumented in the graph
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
  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, NLI->randId);
      if(!(st.hasEdgeAndWt(f)))//addnl
	chords.push_back(f);
    }
  }
}

//Given a tree t, and a "directed graph" g
//replace the edges in the tree t with edges that exist in graph
//The tree is formed from "undirectional" copy of graph
//So whatever edges the tree has, the undirectional graph 
//would have too. This function corrects some of the directions in 
//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){
  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){
      Edge ed(NLI->element, *NI, NLI->weight);
      //if(!g.hasEdge(ed)) t.removeEdge(ed);
      if(!g.hasEdgeAndWt(ed)) t.removeEdge(ed);//tree has only one edge
      //between any pair of vertices, so no need to delete by edge wt
    }
  }
}

//Assign a value to all the edges in the graph
//such that if we traverse along any path from root to exit, and
//add up the edge values, we get a path number that uniquely
//refers to the path we travelled
int valueAssignmentToEdges(Graph& g){
  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(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); RI!=RE; ++RI){
    if(g.isLeaf(*RI))
      NumPaths[*RI]=1;
    else{
      NumPaths[*RI]=0;
      /////
      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];
      }
    }
  }
  return NumPaths[g.getRoot()];
}

//This is a helper function to get the edge increments
//This is used in conjuntion with inc_DFS
//to get the edge increments
//Edge increment implies assigning a value to all the edges in the graph
//such that if we traverse along any path from root to exit, and
//add up the edge values, we get a path number that uniquely
//refers to the path we travelled
//inc_Dir tells whether 2 edges are in same, or in different directions
//if same direction, return 1, else -1
static int inc_Dir(Edge e,