lib/CodeGen/ModuloScheduling/ModuloSchedGraph.cpp

#include <math.h>
#include "ModuloSchedGraph.h"
#include "llvm/CodeGen/InstrSelection.h"
#include "llvm/BasicBlock.h"
#include "llvm/Function.h"
#include "llvm/iOther.h"
#include "Support/StringExtras.h"
#include "Support/STLExtras.h"
#include <iostream>
#include <swig.h>
#include "llvm/iOperators.h"
#include "llvm/iOther.h"
#include "llvm/iPHINode.h"
#include "llvm/iTerminators.h"
#include "llvm/iMemory.h"
#include "llvm/Type.h"
#include "llvm/CodeGen/MachineCodeForInstruction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/Target/MachineSchedInfo.h"

#define UNIDELAY 1
#define min(a, b)       ((a) < (b) ? (a) : (b))
#define max(a, b)       ((a) < (b) ? (b) : (a))

using std::vector;
using std::pair;
//using std::hash_map;
using std::cerr;
extern std::ostream modSched_os;
extern ModuloSchedDebugLevel_t ModuloSchedDebugLevel;
//*********************** Internal Data Structures *************************/

// The following two types need to be classes, not typedefs, so we can use
// opaque declarations in SchedGraph.h
// 
struct RefVec: public vector< pair<ModuloSchedGraphNode*, int> > {
  typedef vector< pair<ModuloSchedGraphNode*, int> >::      iterator       iterator;
  typedef vector< pair<ModuloSchedGraphNode*, int> >::const_iterator const_iterator;
};

struct RegToRefVecMap: public hash_map<int, RefVec> {
  typedef hash_map<int, RefVec>::      iterator       iterator;
  typedef hash_map<int, RefVec>::const_iterator const_iterator;
};

struct ValueToDefVecMap: public hash_map<const Instruction*, RefVec> {
  typedef hash_map<const Instruction*, RefVec>::      iterator       iterator;
  typedef hash_map<const Instruction*, RefVec>::const_iterator const_iterator;
};



// class Modulo SchedGraphNode

/*ctor*/
ModuloSchedGraphNode::ModuloSchedGraphNode(unsigned int _nodeId,
				     const BasicBlock* _bb,
				     const Instruction* _inst,
				     int indexInBB,
				     const TargetMachine& target)
  :
  SchedGraphNodeCommon(_nodeId, _bb, indexInBB),
  inst(_inst)
{
  if(inst)
    {
      //FIXME: find the latency 
      //currently setthe latency to zero
      latency =0;
    }

}
				     
//class ModuloScheGraph


void
ModuloSchedGraph::addDummyEdges()
{
  assert(graphRoot->outEdges.size() == 0);
  
  for (const_iterator I=begin(); I != end(); ++I)
    {
      ModuloSchedGraphNode* node = (ModuloSchedGraphNode*)( (*I).second);
      assert(node != graphRoot && node != graphLeaf);
      if (node->beginInEdges() == node->endInEdges())
	(void) new SchedGraphEdge(graphRoot, node, SchedGraphEdge::CtrlDep,
				  SchedGraphEdge::NonDataDep, 0);
      if (node->beginOutEdges() == node->endOutEdges())
	(void) new SchedGraphEdge(node, graphLeaf, SchedGraphEdge::CtrlDep,
				  SchedGraphEdge::NonDataDep, 0);
    }
}

bool isDefinition(const Instruction* I)
{
  //if(TerminatorInst::classof(I)||FreeInst::classof(I) || StoreInst::classof(I) || CallInst::classof(I))
  if(!I->hasName())
    return false;
  else
    return true;
}

void ModuloSchedGraph::addDefUseEdges(const BasicBlock* bb)
{
  //collect def instructions, store them in vector
  const MachineInstrInfo& mii = target.getInstrInfo();
  
  typedef std::vector<ModuloSchedGraphNode*> DefVec;
  DefVec defVec;
  
  //find those def instructions
  for(BasicBlock::const_iterator I=bb->begin(), E=bb->end(); I !=E; I++)
    if(I->getType() != Type::VoidTy)
      {
	defVec.push_back(this->getGraphNodeForInst(I)) ;
      }
  
  for(unsigned int i=0; i < defVec.size();i++)
    for(Value::use_const_iterator I=defVec[i]->getInst()->use_begin();I !=defVec[i]->getInst()->use_end()  ;I++)
      {
	//for each use of a def, add a flow edge from the def instruction to the ref instruction

	
	const Instruction* value=defVec[i]->getInst();
	Instruction *inst=(Instruction*)(*I);
	ModuloSchedGraphNode* node=NULL;

	for(BasicBlock::const_iterator I=bb->begin(), E=bb->end(); I !=E; I++)
	  if((const Instruction*)I == inst)
	    {
	      node=(*this)[inst];
	      break;
	    }
	
	assert(inst != NULL &&" Use not an Instruction ?" );
	
	if(node == NULL) //inst is not an instruction in this block
	  {}
	else
	  {
	    //add a flow edge from the def instruction to the ref instruction

	    //self loop will not happen in SSA form
      	    assert(defVec[i] != node && "same node?");
	    

	    //this is a true dependence, so the delay is equal to the delay of the pred node.
	    int delay=0;
	    MachineCodeForInstruction& tempMvec=  MachineCodeForInstruction::get(value);
	    for(unsigned j=0;j< tempMvec.size();j++)
	      {
		MachineInstr* temp=tempMvec[j];
		//delay +=mii.minLatency(temp->getOpCode());
		delay = max(delay, mii.minLatency(temp->getOpCode()));
	      }

	    SchedGraphEdge* trueEdge=new SchedGraphEdge(defVec[i],node,value, SchedGraphEdge::TrueDep,delay);

	    //if the ref instruction is before the def instrution
	    //then the def instruction must be a phi instruction 
	    //add an anti-dependence edge to from the ref instruction to the def instruction
	    if( node->getOrigIndexInBB() < defVec[i]->getOrigIndexInBB())
	      {
		assert(PHINode::classof(inst) && "the ref instruction befre def is not PHINode?");
		trueEdge->setIteDiff(1);
	      }
	    
	  }
	
      }
}

void ModuloSchedGraph::addCDEdges(const BasicBlock* bb)
{
  //find the last instruction in the basic block
  //see if it is an branch instruction. 
  //If yes, then add an edge from each node expcept the last node to the last node

  const Instruction* inst=&(bb->back());
  ModuloSchedGraphNode* lastNode=(*this)[inst];
  if( TerminatorInst::classof(inst))
    for(BasicBlock::const_iterator I=bb->begin(),E=bb->end(); I != E; I++)
      {  
	if(inst != I)
	  {
	    ModuloSchedGraphNode* node = (*this)[I];
	    //use latency of 0
	    (void) new SchedGraphEdge(node,lastNode,SchedGraphEdge::CtrlDep,
				      SchedGraphEdge::NonDataDep,0);
	  }
	
      }
 
  
}




static const int SG_LOAD_REF  = 0;
static const int SG_STORE_REF = 1;
static const int SG_CALL_REF  = 2;

static const unsigned int SG_DepOrderArray[][3] = {
  { SchedGraphEdge::NonDataDep,
            SchedGraphEdge::AntiDep,
                        SchedGraphEdge::AntiDep },
  { SchedGraphEdge::TrueDep,
            SchedGraphEdge::OutputDep,
                        SchedGraphEdge::TrueDep | SchedGraphEdge::OutputDep },
  { SchedGraphEdge::TrueDep,
            SchedGraphEdge::AntiDep | SchedGraphEdge::OutputDep,
                        SchedGraphEdge::TrueDep | SchedGraphEdge::AntiDep
                                                | SchedGraphEdge::OutputDep }
};


// Add a dependence edge between every pair of machine load/store/call
// instructions, where at least one is a store or a call.
// Use latency 1 just to ensure that memory operations are ordered;
// latency does not otherwise matter (true dependences enforce that).
// 
void
ModuloSchedGraph::addMemEdges(const BasicBlock* bb)
{
  
  vector<ModuloSchedGraphNode*> memNodeVec;

  //construct the memNodeVec
  
  for( BasicBlock::const_iterator I=bb->begin(), E=bb->end();I != E; I++)
    if(LoadInst::classof(I) ||StoreInst::classof(I) || CallInst::classof(I))
      {
	ModuloSchedGraphNode* node =(*this)[(const Instruction*)I];
	memNodeVec.push_back(node);
      }
  // Instructions in memNodeVec are in execution order within the basic block,
  // so simply look at all pairs <memNodeVec[i], memNodeVec[j: j > i]>.
  // 
  for (unsigned im=0, NM=memNodeVec.size(); im < NM; im++)
    {
      const Instruction* fromInst = memNodeVec[im]->getInst();
      int fromType = CallInst::classof(fromInst)? SG_CALL_REF
	: LoadInst::classof(fromInst)? SG_LOAD_REF
	: SG_STORE_REF;
      for (unsigned jm=im+1; jm < NM; jm++)
	{
	  const Instruction* toInst=memNodeVec[jm]->getInst();
	  int toType = CallInst::classof(toInst)? SG_CALL_REF
	    : LoadInst::classof(toInst)? SG_LOAD_REF
	    : SG_STORE_REF;
          if (fromType != SG_LOAD_REF || toType != SG_LOAD_REF)
	    {
	      (void) new SchedGraphEdge(memNodeVec[im], memNodeVec[jm],
					SchedGraphEdge::MemoryDep,
					SG_DepOrderArray[fromType][toType], 1);
	      
	      SchedGraphEdge* edge=new SchedGraphEdge(memNodeVec[jm],memNodeVec[im],
						      SchedGraphEdge::MemoryDep,
						      SG_DepOrderArray[toType][fromType],1);
	      edge->setIteDiff(1);
	      
	    }
	}
    }
} 



void ModuloSchedGraph::buildNodesforBB  (const TargetMachine& target,
				      const BasicBlock* bb,
				      std::vector<ModuloSchedGraphNode*>& memNode,
				      RegToRefVecMap& regToRefVecMap,
				      ValueToDefVecMap& valueToDefVecMap)
{
  //const MachineInstrInfo& mii=target.getInstrInfo();
  
  //Build graph nodes for each LLVM instruction and gather def/use info.
  //Do both together in a single pass over all machine instructions.
  
  int i=0;
  for(BasicBlock::const_iterator I=bb->begin(), E=bb->end(); I!=E; I++)
    {
      ModuloSchedGraphNode* node=new ModuloSchedGraphNode(getNumNodes(), bb,I,i, target);
      i++;
      this->noteModuloSchedGraphNodeForInst(I,node);
    }

  //this function finds some info about instruction in basic block for later use
  //findDefUseInfoAtInstr(target, node, memNode,regToRefVecMap,valueToDefVecMap);


}


bool ModuloSchedGraph::isLoop(const BasicBlock* bb)
{
  //only if the last instruction in the basicblock is branch instruction and 
  //there is at least an option to branch itself

  
  const Instruction* inst=&(bb->back());
  if( BranchInst::classof(inst))
    for(unsigned i=0;i < ((BranchInst*)inst)->getNumSuccessors();i++)
      {
	BasicBlock* sb=((BranchInst*)inst)->getSuccessor(i);
	if(sb ==bb) return true;
      }
  
  return false;
  
}
bool ModuloSchedGraph::isLoop()
{
  //only if the last instruction in the basicblock is branch instruction and 
  //there is at least an option to branch itself
  
  assert(bbVec.size() ==1 &&"only 1 basicblock in a graph");
  const BasicBlock* bb=bbVec[0];
  const Instruction* inst=&(bb->back());
  if( BranchInst::classof(inst))
    for(unsigned i=0;i < ((BranchInst*)inst)->getNumSuccessors();i++)
      {
	BasicBlock* sb=((BranchInst*)inst)->getSuccessor(i);
	if(sb ==bb) return true;
      }
  
  return false;
  
}

void ModuloSchedGraph::computeNodeASAP(const BasicBlock* bb)
{

 //FIXME: now assume the only backward edges come from the edges from other nodes to the phi Node
  //so i will ignore all edges to the phi node; after this, there shall be no recurrence. 
  
  unsigned numNodes=bb->size();
  for(unsigned i=2;i < numNodes+2;i++)
    {
      ModuloSchedGraphNode* node=getNode(i);
      node->setPropertyComputed(false);
    }

  for(unsigned i=2;i < numNodes+2; i++)
    {
      ModuloSchedGraphNode* node=getNode(i);
      node->ASAP=0;
      if(i==2 ||node->getNumInEdges() ==0) 
	{ node->setPropertyComputed(true);continue;}
      for(ModuloSchedGraphNode::const_iterator I=node->beginInEdges(), E=node->endInEdges();I !=E; I++)
	{
	  SchedGraphEdge* edge=*I;
	  ModuloSchedGraphNode* pred=(ModuloSchedGraphNode*)(edge->getSrc());
	  assert(pred->getPropertyComputed()&&"pred node property is not computed!");
	  int temp=pred->ASAP + edge->getMinDelay() - edge->getIteDiff()*this->MII;
	  node->ASAP= max(node->ASAP,temp);
	}
      node->setPropertyComputed(true);
    }
}

void ModuloSchedGraph::computeNodeALAP(const BasicBlock* bb)
{
  
  unsigned numNodes=bb->size();
  int maxASAP=0;
  for(unsigned i=numNodes+1;i >= 2;i--)
    {
      ModuloSchedGraphNode* node=getNode(i);
      node->setPropertyComputed(false);
      //cerr<< " maxASAP= " <<maxASAP<<" node->ASAP= "<< node->ASAP<<"\n";
      maxASAP=max(maxASAP,node->ASAP);
    }

  //cerr<<"maxASAP is "<<maxASAP<<"\n";
  
  for(unsigned i=numNodes+1;i >= 2; i--)
    {
      ModuloSchedGraphNode* node=getNode(i);
      node->ALAP=maxASAP;
      for(ModuloSchedGraphNode::const_iterator I=node->beginOutEdges(), E=node->endOutEdges(); I!=E; I++)
	{
	  SchedGraphEdge* edge= *I;
	  ModuloSchedGraphNode* succ=(ModuloSchedGraphNode*) (edge->getSink());
	  if(PHINode::classof(succ->getInst()))continue;
	  assert(succ->getPropertyComputed()&&"succ node property is not computed!");
	  int temp=succ->ALAP - edge->getMinDelay()+edge->getIteDiff()*this->MII;
	  node->ALAP =min(node->ALAP,temp);
	}
      node->setPropertyComputed(true);
      
    }
}

void ModuloSchedGraph::computeNodeMov(const BasicBlock* bb)
{
  unsigned numNodes=bb->size();
  for(unsigned i =2;i < numNodes +2 ;i++)
    {
      ModuloSchedGraphNode* node=getNode(i);
      node->mov=node->ALAP-node->ASAP;
      assert(node->mov >=0 &&"move freedom for this node is less than zero? ");
    }
}


void ModuloSchedGraph::computeNodeDepth(const BasicBlock* bb)
{

  unsigned numNodes=bb->size();
  for(unsigned i=2;i < numNodes+2;i++)
    {
      ModuloSchedGraphNode* node=getNode(i);
      node->setPropertyComputed(false);
    }

  for(unsigned i=2;i < numNodes+2; i++)
    {
      ModuloSchedGraphNode* node=getNode(i);
      node->depth=0;
      if(i==2 ||node->getNumInEdges() ==0) 
	{ node->setPropertyComputed(true);continue;}
      for(ModuloSchedGraphNode::const_iterator I=node->beginInEdges(), E=node->endInEdges();I !=E; I++)
	{
	  SchedGraphEdge* edge=*I;
	  ModuloSchedGraphNode* pred=(ModuloSchedGraphNode*)(edge->getSrc());
	  assert(pred->getPropertyComputed()&&"pred node property is not computed!");
	  int temp=pred->depth + edge->getMinDelay();
	  node->depth= max(node->depth,temp);
	}
      node->setPropertyComputed(true);
    }

}


void ModuloSchedGraph::computeNodeHeight(const BasicBlock* bb)
{
  unsigned numNodes=bb->size();
  for(unsigned i=numNodes+1;i >= 2;i--)
    {
      ModuloSchedGraphNode* node=getNode(i);
      node->setPropertyComputed(false);
    }
  
  for(unsigned i=numNodes+1;i >= 2; i--)
    {
      ModuloSchedGraphNode* node=getNode(i);
      node->height=0;
      for(ModuloSchedGraphNode::const_iterator I=node->beginOutEdges(), E=node->endOutEdges(); I!=E; I++)
	{
	  SchedGraphEdge* edge= *I;
	  ModuloSchedGraphNode* succ=(ModuloSchedGraphNode*)(edge->getSink());
	  if(PHINode::classof(succ->getInst())) continue;
	  assert(succ->getPropertyComputed()&&"succ node property is not computed!");
	  node->height=max(node->height, succ->height+edge->getMinDelay());
	  
	}
      node->setPropertyComputed(true);
      
    }

}

void ModuloSchedGraph::computeNodeProperty(const BasicBlock* bb)
{
  //FIXME: now assume the only backward edges come from the edges from other nodes to the phi Node
  //so i will ignore all edges to the phi node; after this, there shall be no recurrence. 
  
  this->computeNodeASAP(bb);
  this->computeNodeALAP(bb);
  this->computeNodeMov(bb);
  this->computeNodeDepth(bb);
  this->computeNodeHeight(bb); 
}


//do not consider the backedge in these two functions:
// i.e. don't consider the edge with destination in phi node
std::vector<ModuloSchedGraphNode*> ModuloSchedGraph::predSet(std::vector<ModuloSchedGraphNode*> set, unsigned backEdgeSrc, unsigned backEdgeSink)
{
  std::vector<ModuloSchedGraphNode*> predS;
  for(unsigned i=0; i < set.size(); i++)
    {
      ModuloSchedGraphNode* node = set[i];
      for(ModuloSchedGraphNode::const_iterator I=node->beginInEdges(), E=node->endInEdges(); I !=E; I++)
	{
	  SchedGraphEdge* edge= *I;
	  if(edge->getSrc()->getNodeId() ==backEdgeSrc && edge->getSink()->getNodeId() == backEdgeSink) continue;
	  ModuloSchedGraphNode* pred= (ModuloSchedGraphNode*)(edge->getSrc());
	  //if pred is not in the predSet, push it in vector
	  bool alreadyInset=false;
	  for(unsigned j=0; j < predS.size(); j++)
	    if(predS[j]->getNodeId() == pred->getNodeId() ) 
	      {alreadyInset=true;break;}
	  
	  for(unsigned j=0; j < set.size(); j++)
	    if(set[j]->getNodeId()  == pred->getNodeId() ) 
	      {alreadyInset=true; break;}
	  
	  if(! alreadyInset)
	    predS.push_back(pred);
	}
    }
  return predS;
}

ModuloSchedGraph::NodeVec ModuloSchedGraph::predSet(NodeVec set)
{
  //node number increases from 2
  return predSet(set,0, 0);
}


std::vector<ModuloSchedGraphNode*> ModuloSchedGraph::predSet(ModuloSchedGraphNode* _node, unsigned backEdgeSrc, unsigned backEdgeSink)
{
  
  std::vector<ModuloSchedGraphNode*> set;
  set.push_back(_node);
  return predSet(set, backEdgeSrc, backEdgeSink);

}

std::vector<ModuloSchedGraphNode*> ModuloSchedGraph::predSet(ModuloSchedGraphNode* _node)
{
  return predSet(_node,0,0);
}

std::vector<ModuloSchedGraphNode*> ModuloSchedGraph::succSet(std::vector<ModuloSchedGraphNode*> set,unsigned src, unsigned sink)
{
  vector<ModuloSchedGraphNode*> succS;
  for(unsigned i=0; i < set.size(); i++)
    {
      ModuloSchedGraphNode* node = set[i];
      for(ModuloSchedGraphNode::const_iterator I=node->beginOutEdges(), E=node->endOutEdges(); I !=E; I++)
	{
	  SchedGraphEdge* edge= *I;
	  if(edge->getSrc()->getNodeId() == src && edge->getSink()->getNodeId() == sink) continue;
	  ModuloSchedGraphNode* succ= (ModuloSchedGraphNode*)(edge->getSink());
	  //if pred is not in the predSet, push it in vector
	  bool alreadyInset=false;
	  for(unsigned j=0; j < succS.size(); j++)
	    if(succS[j]->getNodeId() == succ->getNodeId() ) 
	      {alreadyInset=true;break;}

	  for(unsigned j=0; j < set.size(); j++)
	    if(set[j]->getNodeId() == succ->getNodeId() ) 
	      {alreadyInset=true;break;}
	  if(! alreadyInset)
	    succS.push_back(succ);
	}
    }
  return succS; 
}

ModuloSchedGraph::NodeVec ModuloSchedGraph::succSet(NodeVec set)
{
  return succSet(set,0,0);
}


std::vector<ModuloSchedGraphNode*> ModuloSchedGraph::succSet(ModuloSchedGraphNode* _node,unsigned src, unsigned sink)
{
  std::vector<ModuloSchedGraphNode*> set;
  set.push_back(_node);
  return succSet(set, src, sink);
  
  
}

std::vector<ModuloSchedGraphNode*> ModuloSchedGraph::succSet(ModuloSchedGraphNode* _node)
{
  return succSet(_node, 0, 0);
}

SchedGraphEdge* ModuloSchedGraph::getMaxDelayEdge(unsigned srcId, unsigned sinkId)
{
  
  ModuloSchedGraphNode* node =getNode(srcId);
  SchedGraphEdge* maxDelayEdge=NULL;
  int maxDelay=-1;
  for(ModuloSchedGraphNode::const_iterator I=node->beginOutEdges(), E=node->endOutEdges();I !=E; I++)
    {
      SchedGraphEdge* edge= *I;
      if(edge->getSink()->getNodeId() == sinkId)
	if(edge->getMinDelay() > maxDelay){
	  maxDelayEdge=edge;
	  maxDelay=edge->getMinDelay(); 
	}
    }
  assert(maxDelayEdge != NULL&&"no edge between the srcId and sinkId?");
  return maxDelayEdge;
}

void ModuloSchedGraph::dumpCircuits()
{
  modSched_os<<"dumping circuits for graph: "<<"\n";
  int j=-1;
  while(circuits[++j][0] !=0){
    int k=-1;
    while(circuits[j][++k] !=0)
      modSched_os<< circuits[j][k]<<"\t";
    modSched_os<<"\n";
  }
}

void ModuloSchedGraph::dumpSet(std::vector<ModuloSchedGraphNode*> set)
{
  for(unsigned i=0;i < set.size() ; i++)
    modSched_os<< set[i]->getNodeId()<<"\t";
  modSched_os<<"\n";
}

std::vector<ModuloSchedGraphNode*> ModuloSchedGraph::vectorUnion(std::vector<ModuloSchedGraphNode*> set1,std::vector<ModuloSchedGraphNode*> set2 )
{
  std::vector<ModuloSchedGraphNode*> unionVec;
  for(unsigned i=0;i<set1.size();i++)
    unionVec.push_back(set1[i]);
  for(unsigned j=0;j < set2.size();j++){
    bool inset=false;
    for(unsigned i=0;i < unionVec.size();i++)
      if(set2[j]==unionVec[i]) inset=true;
    if(!inset)unionVec.push_back(set2[j]);
  }
  return unionVec;
}
std::vector<ModuloSchedGraphNode*> ModuloSchedGraph::vectorConj(std::vector<ModuloSchedGraphNode*> set1,std::vector<ModuloSchedGraphNode*> set2 )
{
   std::vector<ModuloSchedGraphNode*> conjVec;
  for(unsigned i=0;i<set1.size();i++)
    for(unsigned j=0;j < set2.size();j++)
      if(set1[i]==set2[j]) conjVec.push_back(set1[i]);
  return conjVec; 
}

ModuloSchedGraph::NodeVec ModuloSchedGraph::vectorSub(NodeVec set1, NodeVec set2)
{
  NodeVec newVec;
  for(NodeVec::iterator I=set1.begin(); I != set1.end(); I++){
    bool inset=false;
    for(NodeVec::iterator II=set2.begin(); II!=set2.end(); II++)
      if( (*I)->getNodeId() ==(*II)->getNodeId()) 
	{inset=true;break;}
    if(!inset) newVec.push_back(*I);
  }
  return newVec;
}
  
void ModuloSchedGraph::orderNodes(){
  oNodes.clear();
  
  std::vector<ModuloSchedGraphNode*> set;
  const BasicBlock* bb=bbVec[0];
  unsigned numNodes = bb->size();
  
  //first order all the sets
  int j=-1;
  int totalDelay=-1;
  int preDelay=-1;
  while(circuits[++j][0] !=0){
    int k=-1;
    preDelay=totalDelay;

    while(circuits[j][++k] !=0){
      ModuloSchedGraphNode* node =getNode(circuits[j][k]);
      unsigned nextNodeId;
      nextNodeId =circuits[j][k+1] !=0? circuits[j][k+1]:circuits[j][0];
      SchedGraphEdge* edge = getMaxDelayEdge(circuits[j][k], nextNodeId);
      totalDelay += edge->getMinDelay();
    }
    if(preDelay != -1 && totalDelay > preDelay){
      //swap circuits[j][] and cuicuits[j-1][]
      unsigned temp[MAXNODE];
      for(int k=0;k<MAXNODE;k++){
	temp[k]=circuits[j-1][k];	
	circuits[j-1][k]=circuits[j][k];
	circuits[j][k]=temp[k];
      }
      //restart
      j=-1;
    }
  }

  //build the first set
  int backEdgeSrc;
  int backEdgeSink;
  if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
    modSched_os<<"building the first set"<<"\n";
  int setSeq=-1;
  int k=-1;
  setSeq++;
  while(circuits[setSeq][++k]!=0)
    set.push_back(getNode(circuits[setSeq][k]));
  if(circuits[setSeq][0]!=0){
    backEdgeSrc=circuits[setSeq][k-1];
    backEdgeSink=circuits[setSeq][0];
  }
  if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess){
    modSched_os<<"the first set is:";
    dumpSet(set);
  }
  
  //implement the ordering algorithm
  enum OrderSeq{ bottom_up, top_down};
  OrderSeq order;
  std::vector<ModuloSchedGraphNode*> R;
  while(!set.empty())
    {
      std::vector<ModuloSchedGraphNode*> pset=predSet(oNodes);
      std::vector<ModuloSchedGraphNode*> sset=succSet(oNodes);
      
      if(!pset.empty() && !vectorConj(pset,set).empty())
	{R=vectorConj(pset,set);order=bottom_up;}
      else if( !sset.empty() && !vectorConj(sset,set).empty())
	{R=vectorConj(sset,set);order=top_down;}
      else
	{
	  int maxASAP=-1;
	  int position=-1;
	  for(unsigned i=0;i<set.size();i++){
	    int temp= set[i]->getASAP();
	    if(temp>maxASAP ) {
	      maxASAP=temp;
	      position=i;
	    }
	  }
	  R.push_back(set[position]);
	  order=bottom_up;	
	}
      
      while(!R.empty()){
	if(order== top_down){
	  if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
	    modSched_os<<"in top_down round"<<"\n";
	  while(!R.empty()){
	    int maxHeight=-1;
	    NodeVec::iterator chosenI;
	    for(NodeVec::iterator I=R.begin();I != R.end();I++){
	      int temp=(*I)->height;
	      if( (temp > maxHeight) || ( temp == maxHeight && (*I)->mov <= (*chosenI)->mov ) ){
		
		if((temp > maxHeight) || ( temp == maxHeight && (*I)->mov < (*chosenI)->mov )){
		  maxHeight=temp;
		  chosenI=I;
		  continue;
		}
		//possible case: instruction A and B has the same height and mov, but A has dependence to B
		//e.g B is the branch instruction in the end, or A is the phi instruction at the beginning
		if((*I)->mov == (*chosenI)->mov)
		  for(ModuloSchedGraphNode::const_iterator oe=(*I)->beginOutEdges(), end=(*I)->endOutEdges();oe !=end; oe++){
		    if((*oe)->getSink() == (*chosenI)){
		      maxHeight=temp;
		      chosenI=I;
		      continue;
		    }
		  }
	      }
	    }
	    ModuloSchedGraphNode* mu= *chosenI;
	    oNodes.push_back(mu);
	    R.erase(chosenI);
	    std::vector<ModuloSchedGraphNode*> succ_mu= succSet(mu,backEdgeSrc,backEdgeSink);
	      std::vector<ModuloSchedGraphNode*> comm=vectorConj(succ_mu,set);
	      comm=vectorSub(comm,oNodes);
	    R = vectorUnion(comm, R);
	  }
	  order=bottom_up;
	  R= vectorConj(predSet(oNodes), set);
	} else{
	  if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
	    modSched_os<<"in bottom up round"<<"\n";
	  while(!R.empty()){
	    int maxDepth=-1;
	    NodeVec::iterator chosenI;
	    for(NodeVec::iterator I=R.begin();I != R.end();I++){
	      int temp=(*I)->depth;
	      if( (temp > maxDepth) || ( temp == maxDepth && (*I)->mov < (*chosenI)->mov )){
		maxDepth=temp;
		chosenI=I;
	      }
	    }
	    ModuloSchedGraphNode* mu=*chosenI;
	    oNodes.push_back(mu);
	    R.erase(chosenI);
	    std::vector<ModuloSchedGraphNode*> pred_mu= predSet(mu,backEdgeSrc,backEdgeSink);
	    std::vector<ModuloSchedGraphNode*> comm=vectorConj(pred_mu,set);
	    comm=vectorSub(comm,oNodes);
	    R = vectorUnion(comm, R);
	  }
	  order=top_down;
	  R= vectorConj(succSet(oNodes), set);
	}
      }
      if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess){
	modSched_os<<"order finished"<<"\n";
	modSched_os<<"dumping the ordered nodes: "<<"\n";
	dumpSet(oNodes);
	dumpCircuits();
      }
      //create a new set
      //FIXME: the nodes between onodes and this circuit should also be include in this set
      if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
	modSched_os<<"building the next set"<<"\n";
      set.clear();
      int k=-1;
      setSeq++;
      while(circuits[setSeq][++k]!=0)
	set.push_back(getNode(circuits[setSeq][k]));
      if(circuits[setSeq][0]!=0){
	backEdgeSrc=circuits[setSeq][k-1];
	backEdgeSink=circuits[setSeq][0];
      }
      if(set.empty()){
	//no circuits any more
	//collect all other nodes
	if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
	  modSched_os<<"no circuits any more, collect the rest nodes"<<"\n";
	for(unsigned i=2;i<numNodes+2;i++){
	  bool inset=false;
	  for(unsigned j=0;j< oNodes.size();j++)
	    if(oNodes[j]->getNodeId() == i) 
	      {inset=true;break;}
	  if(!inset)set.push_back(getNode(i));
	}
      }
      if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess){
	modSched_os<<"next set is: "<<"\n";
	dumpSet(set);
      }
    }//while(!set.empty())
  
}






void ModuloSchedGraph::buildGraph (const TargetMachine& target)
{
  const BasicBlock* bb=bbVec[0]; 

  assert(bbVec.size() ==1 &&"only handling a single basic block here");

  // Use this data structure to note all machine operands that compute
  // ordinary LLVM values.  These must be computed defs (i.e., instructions). 
  // Note that there may be multiple machine instructions that define
  // each Value.
  ValueToDefVecMap valueToDefVecMap;

  // Use this data structure to note all memory instructions.
  // We use this to add memory dependence edges without a second full walk.
  // 
  // vector<const Instruction*> memVec;
  vector<ModuloSchedGraphNode*> memNodeVec;

   // Use this data structure to note any uses or definitions of
  // machine registers so we can add edges for those later without
  // extra passes over the nodes.
  // The vector holds an ordered list of references to the machine reg,
  // ordered according to control-flow order.  This only works for a
  // single basic block, hence the assertion.  Each reference is identified
  // by the pair: <node, operand-number>.
  // 
  RegToRefVecMap regToRefVecMap;
  


 // Make a dummy root node.  We'll add edges to the real roots later.
  graphRoot = new ModuloSchedGraphNode(0, NULL, NULL, -1,target);
  graphLeaf = new ModuloSchedGraphNode(1, NULL, NULL, -1,target);
 
 //----------------------------------------------------------------
  // First add nodes for all the LLVM instructions in the basic block
  // because this greatly simplifies identifying which edges to add.
  // Do this one VM instruction at a time since the ModuloSchedGraphNode needs that.
  // Also, remember the load/store instructions to add memory deps later.
  //----------------------------------------------------------------

  //FIXME:if there is call instruction, then we shall quit somewhere
  //      currently we leave call instruction and continue construct graph

  //dump only the blocks which are from loops


  if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
    this->dump(bb);

  if(!isLoop(bb)){
    modSched_os <<" dumping non-loop BB:"<<endl;
    dump(bb);
  }
  if( isLoop(bb))
    {
      buildNodesforBB(target, bb, memNodeVec, regToRefVecMap, valueToDefVecMap);
      
      this->addDefUseEdges(bb);
      
      this->addCDEdges(bb);
      
      this->addMemEdges(bb);
      
      //this->dump();
      
      int ResII=this->computeResII(bb);
      if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
	modSched_os << "ResII is " << ResII<<"\n";;
      int RecII=this->computeRecII(bb);      
      if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
	modSched_os << "RecII is " <<RecII<<"\n";
      
      this->MII=max(ResII, RecII);
      
      this->computeNodeProperty(bb);
      if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
	this->dumpNodeProperty();
      
      this->orderNodes();
      
      if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
	this->dump();
      //this->instrScheduling();
      
      //this->dumpScheduling();
      
      
    }
}

ModuloSchedGraphNode* ModuloSchedGraph::getNode  (const unsigned nodeId) const
{
  for(const_iterator I=begin(), E=end();I !=E;I++)
    if((*I).second->getNodeId() ==nodeId)
      return (ModuloSchedGraphNode*)(*I).second;
  return NULL;
}

int ModuloSchedGraph::computeRecII(const BasicBlock* bb)
{

  int  RecII=0;

  //os<<"begining computerRecII()"<<"\n";


  //FIXME: only deal with circuits starting at the first node: the phi node nodeId=2;

  //search all elementary circuits in the dependance graph
  //assume maximum number of nodes is MAXNODE
  
  unsigned path[MAXNODE];
  unsigned stack[MAXNODE][MAXNODE];


  for(int j=0;j<MAXNODE;j++)
    {path[j]=0;
    for(int k=0;k<MAXNODE;k++)
      stack[j][k]=0;
    }
  //in our graph, the node number starts at 2

  //number of nodes, because each instruction will result in one node
  const unsigned numNodes= bb->size();
  
  int i=0;
  path[i]=2;

  ModuloSchedGraphNode* initNode=getNode(path[0]);
  unsigned initNodeId=initNode->getNodeId();
  ModuloSchedGraphNode* currentNode=initNode;
  
  while(currentNode != NULL)
    {
      unsigned currentNodeId=currentNode->getNodeId();
      //      modSched_os<<"current node is "<<currentNodeId<<"\n";
      
      ModuloSchedGraphNode* nextNode=NULL;
      for(ModuloSchedGraphNode::const_iterator I=currentNode->beginOutEdges(), E=currentNode->endOutEdges(); I !=E; I++)
	{
	  //modSched_os <<" searching in outgoint edges of node "<<currentNodeId<<"\n";
	  unsigned nodeId=((SchedGraphEdge*) *I)->getSink()->getNodeId();
	  bool inpath=false,instack=false;
	  int k;

	  //modSched_os<<"nodeId is "<<nodeId<<"\n";

	  k=-1;
	  while(path[++k] !=0)
	    if(nodeId == path[k])
	      {inpath=true;break;}
	  


	  k=-1;
	  while(stack[i][++k] !=0 )
	    if(nodeId == stack[i][k])
	      {instack =true; break;}


	  if( nodeId > currentNodeId && !inpath && !instack)
	    {nextNode=(ModuloSchedGraphNode*) ((SchedGraphEdge*)*I)->getSink();break;}
	  
	}
      if(nextNode != NULL)
	{
	  //modSched_os<<"find the next Node "<<nextNode->getNodeId()<<"\n";
	  
	  
	  int j=0;
	  while( stack[i][j] !=0) j++;
	  stack[i][j]=nextNode->getNodeId();


	  i++;
	  path[i]=nextNode->getNodeId();
	  currentNode=nextNode;
	}
      else
	{
	  //modSched_os<<"no expansion any more"<<"\n";
	  //confirmCircuit();
	  for(ModuloSchedGraphNode::const_iterator I=currentNode->beginOutEdges(), E=currentNode->endOutEdges() ; I != E; I++)
	    {
	      unsigned nodeId=((SchedGraphEdge*)*I)->getSink()->getNodeId();
	      if(nodeId == initNodeId)
		{

		  int j=-1;
		  while(circuits[++j][0] !=0);
		  for(int k=0;k<MAXNODE;k++)circuits[j][k]=path[k];

		}
	    }
	  //remove this node in the path and clear the corresponding entries in the stack
	  path[i]=0;
	  int j=0;
	  for(j=0;j<MAXNODE;j++)stack[i][j]=0;
	  i--;
	  currentNode=getNode(path[i]);
	}
      if(i==0) 
	{

	  if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
	    modSched_os<<"circuits found are: "<<"\n";
	  int j=-1;
	  while(circuits[++j][0] !=0){
	    int k=-1;
	    while(circuits[j][++k] !=0)
	      if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
		modSched_os<< circuits[j][k]<<"\t";
	    if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
	      modSched_os<<"\n";
	  
	    
	    //for this circuit, compute the sum of all edge delay
	    int sumDelay=0;
	    k=-1;
	    while(circuits[j][++k] !=0)
	      {
		//ModuloSchedGraphNode* node =getNode(circuits[j][k]);
		unsigned nextNodeId;
		nextNodeId =circuits[j][k+1] !=0? circuits[j][k+1]:circuits[j][0];

		/*
		for(ModuloSchedGraphNode::const_iterator I=node->beginOutEdges(), E=node->endOutEdges();I !=E; I++)
		{
		  SchedGraphEdge* edge= *I;
		    if(edge->getSink()->getNodeId() == nextNodeId)
		    {sumDelay  += edge->getMinDelay();break;}
		      }
		*/

		sumDelay += getMaxDelayEdge(circuits[j][k],nextNodeId)->getMinDelay();

	      }
	    //       assume we have distance 1, in this case the sumDelay is RecII
	    //       this is correct for SSA form only
	    //      
	    if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
	      modSched_os<<"The total Delay in the circuit is " <<sumDelay<<"\n";
	    
	    RecII= RecII > sumDelay? RecII: sumDelay;
	    
	  }
	  return RecII;
	}
      
    }
  
  return -1;
}

void  ModuloSchedGraph::addResourceUsage(std::vector<pair<int,int> >& ruVec, int rid){
  //modSched_os<<"\nadding a resouce , current resouceUsage vector size is "<<ruVec.size()<<"\n";
  bool alreadyExists=false;
  for(unsigned i=0;i <ruVec.size() ; i++){
    if(rid == ruVec[i].first) {
      ruVec[i].second++;
      alreadyExists=true;
      break;
    }
  }
  if( !alreadyExists) ruVec.push_back(std::make_pair(rid, 1));
  //modSched_os<<"current resouceUsage vector size is "<<ruVec.size()<<"\n";

}
void ModuloSchedGraph::dumpResourceUsage(std::vector< pair<int,int> > &ru)
{
  MachineSchedInfo& msi = (MachineSchedInfo&)target.getSchedInfo();
  
  std::vector<pair<int,int> > resourceNumVector = msi.resourceNumVector;
  modSched_os <<"resourceID\t"<<"resourceNum"<<"\n";
  for(unsigned i=0;i<resourceNumVector.size();i++)
    modSched_os <<resourceNumVector[i].first<<"\t"<<resourceNumVector[i].second<<"\n";
  
  modSched_os <<" maxNumIssueTotal(issue slot in one cycle) = "<<msi.maxNumIssueTotal<<"\n";
  modSched_os<<"resourceID\t resourceUsage\t ResourceNum"<<"\n";
  for(unsigned i=0;i<ru.size();i++){
    modSched_os<<ru[i].first<<"\t"<<ru[i].second;
    const unsigned  resNum=msi.getCPUResourceNum(ru[i].first);
    modSched_os<<"\t"<<resNum<<"\n";
  }
}

int ModuloSchedGraph::computeResII(const BasicBlock* bb)
{
  
  const MachineInstrInfo& mii = target.getInstrInfo();
  const MachineSchedInfo& msi = target.getSchedInfo();
  
  int ResII;
  std::vector<pair<int,int> > resourceUsage; //pair<int resourceid, int resourceUsageTimes_in_the_whole_block>
  
  //FIXME: number of functional units the target machine can provide should be get from Target
  //       here I temporary hardcode it
  
  for(BasicBlock::const_iterator I=bb->begin(),E=bb->end(); I !=E; I++)
    {
      if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess){
	modSched_os<<"machine instruction for llvm instruction( node "<<getGraphNodeForInst(I)->getNodeId()<<")" <<"\n";
	modSched_os<<"\t"<<*I;
      }
      MachineCodeForInstruction& tempMvec=  MachineCodeForInstruction::get(I);
      if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
	modSched_os <<"size =" <<tempMvec.size()<<"\n";
      for(unsigned i=0;i< tempMvec.size();i++)
	{
	  MachineInstr* minstr=tempMvec[i];
	  
	  unsigned minDelay=mii.minLatency(minstr->getOpCode());
	  InstrRUsage rUsage=msi.getInstrRUsage(minstr->getOpCode());
	  InstrClassRUsage classRUsage=msi.getClassRUsage(mii.getSchedClass(minstr->getOpCode()));
	  unsigned totCycles= classRUsage.totCycles;
	  
	  std::vector<std::vector<resourceId_t> > resources
	    =rUsage.resourcesByCycle;
	  assert(totCycles == resources.size());
	  if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
	    modSched_os <<"resources Usage for this Instr(totCycles=" << totCycles << ",mindLatency="<<mii.minLatency(minstr->getOpCode())<<"): "<< *minstr <<"\n";
	  for(unsigned j=0;j< resources.size();j++){
	    if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
	      modSched_os<<"cycle "<<j<<": ";
	    for(unsigned k=0;k< resources[j].size(); k++){
	      if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
		modSched_os<<"\t"<<resources[j][k];
	      addResourceUsage(resourceUsage,resources[j][k]);
	    }
	    if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)
	      modSched_os<<"\n";
	  }
	}  
    }
  if(ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess)  
    this->dumpResourceUsage(resourceUsage);

  //compute ResII
  ResII=0;
  int issueSlots=msi.maxNumIssueTotal;
  for(unsigned i=0;i<resourceUsage.size();i++){
    int resourceNum=msi.getCPUResourceNum(resourceUsage[i].first);
    int useNum=resourceUsage[i].second;
    double tempII;
    if(resourceNum <= issueSlots)
      tempII=ceil(1.0*useNum/resourceNum);
    else
      tempII=ceil(1.0*useNum/issueSlots);
    ResII=max((int)tempII,ResII);
  }
  return ResII;
}

ModuloSchedGraphSet::ModuloSchedGraphSet(const Function* function, const TargetMachine& target)
  :method(function)
{
  buildGraphsForMethod(method,target);
  
}


ModuloSchedGraphSet::~ModuloSchedGraphSet()
{
  //delete all the graphs
  for(iterator I=begin(), E=end();I !=E; ++I)
    delete *I;
}

void ModuloSchedGraphSet::dump() const 
{
  modSched_os << " ====== ModuloSched graphs for function `" <<method->getName()
       << "' =========\n\n";
  for(const_iterator I=begin(); I != end(); ++I)
    (*I)->dump();
    
  modSched_os << "\n=========End graphs for funtion` "<<method->getName()
       << "' ==========\n\n";
}

void ModuloSchedGraph::dump(const BasicBlock* bb)
{
  modSched_os<<"dumping basic block:";
  modSched_os<<(bb->hasName()?bb->getName(): "block")
      <<" (" << bb << ")"<<"\n";

}

void ModuloSchedGraph::dump(const BasicBlock* bb, std::ostream& os)
{
  os<<"dumping basic block:";
  os<<(bb->hasName()?bb->getName(): "block")
    <<" (" << bb << ")"<<"\n";
}

void 
ModuloSchedGraph::dump() const
{
  modSched_os << " ModuloSchedGraph for basic Blocks:";
  for(unsigned i=0, N =bbVec.size(); i< N; i++)
    {
      modSched_os<<(bbVec[i]->hasName()?bbVec[i]->getName(): "block")
	  <<" (" << bbVec[i] << ")"
	  << ((i==N-1)?"":", ");
    }
  
  modSched_os <<"\n\n    Actual Root nodes : ";
  for (unsigned i=0, N=graphRoot->outEdges.size(); i < N; i++)
    modSched_os << graphRoot->outEdges[i]->getSink()->getNodeId()
	 << ((i == N-1)? "" : ", ");

  modSched_os << "\n    Graph Nodes:\n";
  //for (const_iterator I=begin(); I != end(); ++I)
  //modSched_os << "\n" << *I->second;
  unsigned numNodes=bbVec[0]->size();
  for(unsigned i=2;i< numNodes+2;i++)
    {
      ModuloSchedGraphNode* node= getNode(i);
      modSched_os << "\n" << *node;
    }

  modSched_os << "\n";
}
void 
ModuloSchedGraph::dumpNodeProperty() const
{
  const BasicBlock* bb=bbVec[0];
  unsigned numNodes=bb->size();
  for(unsigned i=2;i < numNodes+2;i++)
    { 
      ModuloSchedGraphNode* node=getNode(i);
      modSched_os<<"NodeId "<<node->getNodeId()<<"\t";
      modSched_os<<"ASAP "<<node->getASAP()<<"\t";
      modSched_os<<"ALAP "<<node->getALAP()<<"\t";
      modSched_os<<"mov " <<node->getMov() <<"\t";
      modSched_os<<"depth "<<node->getDepth()<<"\t";
      modSched_os<<"height "<<node->getHeight()<<"\t";
      modSched_os<<"\n";
    }
}

void ModuloSchedGraphSet::buildGraphsForMethod (const Function *F, const TargetMachine& target)
{
  for(Function::const_iterator BI = F->begin(); BI != F->end(); ++BI)
    addGraph(new ModuloSchedGraph(BI,target));
}

std::ostream &operator<<(std::ostream &os, const ModuloSchedGraphNode& node)
{
  os << std::string(8, ' ')
     << "Node " << node.nodeId << " : "
     << "latency = " << node.latency << "\n" << std::string(12, ' ');
  


  if (node.getInst() == NULL)
    os << "(Dummy node)\n";
  else
    {
      os << *node.getInst() << "\n" << std::string(12, ' ');
      os << node.inEdges.size() << " Incoming Edges:\n";
      for (unsigned i=0, N=node.inEdges.size(); i < N; i++)
	os << std::string(16, ' ') << *node.inEdges[i];
  
      os << std::string(12, ' ') << node.outEdges.size()
         << " Outgoing Edges:\n";
      for (unsigned i=0, N=node.outEdges.size(); i < N; i++)
        os << std::string(16, ' ') << *node.outEdges[i];
    }
  

  return os;
}