Putting my revised version of ModuloScheduling in cvs. This is not complete...

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8179 91177308-0d34-0410-b5e6-96231b3b80d8

8 files changed, 310 insertions, 5880 deletions

diff --git a/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.cpp b/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.cpp
index a29722aa61..1bdbb1a976 100644
--- a/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.cpp
+++ b/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.cpp
@@ -1,1507 +1,130 @@
-//===- ModuloSchedGraph.cpp - Graph datastructure for Modulo Scheduling ---===//
-//
-//
+//===- ModuloSchedGraph.cpp - Modulo Scheduling Graph and Set -*- C++ -*---===//
+// 
+// Description here
 //===----------------------------------------------------------------------===//
 
-#include "llvm/CodeGen/InstrSelection.h"
-#include "llvm/Function.h"
-#include "llvm/Instructions.h"
-#include "llvm/Type.h"
-#include "llvm/CodeGen/MachineCodeForInstruction.h"
-#include "llvm/CodeGen/MachineInstr.h"
-#include "llvm/Target/TargetSchedInfo.h"
-#include "Support/StringExtras.h"
-#include "Support/STLExtras.h"
-#include "Support/hash_map"
-#include "Support/Statistic.h"
-#include "ModuloScheduling.h"
 #include "ModuloSchedGraph.h"
-#include <algorithm>
-#include <ostream>
-#include <vector>
-#include <math.h>
-
-
-#define UNIDELAY 1
-
-using std::cerr;
-using std::endl;
-using std::vector;
-
-
-/***********member functions for ModuloSchedGraphNode*********/
-
-
-ModuloSchedGraphNode::ModuloSchedGraphNode(unsigned int in_nodeId,
-                                           const BasicBlock * in_bb,
-                                           const Instruction * in_inst,
-                                           int indexInBB,
-                                           const TargetMachine & target)
-  :SchedGraphNodeCommon(in_nodeId, indexInBB), inst(in_inst){
-  
-  if (inst) {
-    //FIXME: find the latency 
-    //currently set the latency to zero
-    latency = 0;
-  }
-}
-
-
-/***********member functions for ModuloSchedGraph*********/
-
-void 
-ModuloSchedGraph::addDefUseEdges(const BasicBlock *bb){
-  
-  //collect def instructions, store them in vector
-  const TargetInstrInfo & mii = target.getInstrInfo();
-  vector < ModuloSchedGraphNode * > 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 ins = bb->begin(), E = bb->end();
-           ins != E; ++ins)
-        if ((const Instruction *) ins == inst) {
-          node = (*this)[inst];
-          break;
-        }
-
-
-      if (node == NULL){
-	
-	//inst is not an instruction in this block
-	//do nothing
-
-      } else {
-        // Add a flow edge from the def instruction to the ref instruction
-	// This is a true dependence, so the delay is equal to the 
-	//delay of the preceding node.
-	
-        int delay = 0;
-	
-        // self loop will not happen in SSA form
-        assert(defVec[i] != node && "same node?");
-
-        MachineCodeForInstruction & tempMvec =
-            MachineCodeForInstruction::get(value);
-        for (unsigned j = 0; j < tempMvec.size(); j++) {
-          MachineInstr *temp = tempMvec[j];
-          delay = std::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,*toInst;
-    int toType, fromType;
-    
-    //get the first mem instruction and instruction type
-    fromInst = memNodeVec[im]->getInst();
-    fromType = CallInst::classof(fromInst) ? SG_CALL_REF
-      : LoadInst::classof(fromInst) ? SG_LOAD_REF : SG_STORE_REF;
-    
-    for (unsigned jm = im + 1; jm < NM; jm++) {
-      
-      //get the second mem instruction and instruction type
-      toInst = memNodeVec[jm]->getInst();
-      toType = CallInst::classof(toInst) ? SG_CALL_REF
-          : LoadInst::classof(toInst) ? SG_LOAD_REF : SG_STORE_REF;
-      
-      //add two edges if not both of them are LOAD instructions
-      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);
-
-	//set the iteration difference for this edge to 1.
-        edge->setIteDiff(1);
-	
-      }
-    }
-  }
-}
-
-/*
-  this function build graph nodes for each instruction 
-  in the basicblock
-*/
-
-void 
-ModuloSchedGraph::buildNodesforBB(const TargetMachine &target,
-				  const BasicBlock *bb){
-  
-  int i = 0;
-  ModuloSchedGraphNode *node;
-
-  for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); 
-       I != E; ++I) {
-    
-    node=new ModuloSchedGraphNode(getNumNodes(), bb, I, i, target);
-    
-    i++;
-    
-    this->addHash(I, node);
-  }
-
-}
-
-
-/*
-  determine if this basicblock includes a loop or not
-*/
-
-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;
-
-}
-
-/*
-  compute every node's ASAP
-
-*/
-
-//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.
-
-void 
-ModuloSchedGraph::computeNodeASAP(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->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 = std::max(node->ASAP, temp);
-    }
-    node->setPropertyComputed(true);
-  }
-}
-
-
-/*
-  compute every node's ALAP in the basic block
-*/
-
-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);
-    maxASAP = std::max(maxASAP, node->ASAP);
-
-  }
-
-  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 = std::min(node->ALAP, temp);
-      
-    }
-    node->setPropertyComputed(true);
-  }
-}
-
-/*
-  compute every node's mov in this basicblock
-*/
-
-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? ");
-    
-  }
-
-}
-
-
-/*
-  compute every node's depth in this basicblock
-*/
-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 = std::max(node->depth, temp);
-    }
-    node->setPropertyComputed(true);
-
-  }
-  
-}
-
-
-/*
-  compute every node's height in this basic block
-*/
-
-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 = std::max(node->height, succ->height + edge->getMinDelay());
-      
-    }
-    node->setPropertyComputed(true);
-  }
-  
-}
-
-/*
-  compute every node's property in a basicblock
-*/
-
-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);
-}
-
-
-/*
-  compute the preset of this set without considering the edges
-  between backEdgeSrc and backEdgeSink
-*/
-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 edges between backEdgeSrc and backEdgeSink, omitted
-      if (edge->getSrc()->getNodeId() == backEdgeSrc
-          && edge->getSink()->getNodeId() == backEdgeSink)
-        continue;
-      ModuloSchedGraphNode *pred =
-          (ModuloSchedGraphNode *) (edge->getSrc());
-
-      //if pred is not in the predSet ....
-      bool alreadyInset = false;
-      for (unsigned j = 0; j < predS.size(); ++j)
-        if (predS[j]->getNodeId() == pred->getNodeId()) {
-          alreadyInset = true;
-          break;
-        }
-
-      // and pred is not in the set ....
-      for (unsigned j = 0; j < set.size(); ++j)
-        if (set[j]->getNodeId() == pred->getNodeId()) {
-          alreadyInset = true;
-          break;
-        }
-
-      //push it into the predS
-      if (!alreadyInset)
-        predS.push_back(pred);
-    }
-  }
-  return predS;
-}
-
-
-/*
-  return pred set to this set
-*/
-
-ModuloSchedGraph::NodeVec 
-ModuloSchedGraph::predSet(NodeVec set){
-  
-  //node number increases from 2,   
-  return predSet(set, 0, 0);
-}
-
-/*
-  return pred set to  _node, ignoring 
-  any edge between backEdgeSrc and backEdgeSink
-*/
-std::vector <ModuloSchedGraphNode*>
-ModuloSchedGraph::predSet(ModuloSchedGraphNode *_node,
-                          unsigned backEdgeSrc, unsigned backEdgeSink){
-
-  std::vector<ModuloSchedGraphNode*> set;
-  set.push_back(_node);
-  return predSet(set, backEdgeSrc, backEdgeSink);
-}
-
-
-/*
-  return pred set to  _node, ignoring 
-*/
-
-std::vector <ModuloSchedGraphNode*>
-ModuloSchedGraph::predSet(ModuloSchedGraphNode * _node){
-  
-  return predSet(_node, 0, 0);
-  
-}
-
-/*
-  return successor set to the input set
-  ignoring any edge between src and sink
-*/
-
-std::vector<ModuloSchedGraphNode*>
-ModuloSchedGraph::succSet(std::vector<ModuloSchedGraphNode*> set, 
-                          unsigned src, unsigned sink){
-  
-  std::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 the edge is between src and sink, skip
-      if (edge->getSrc()->getNodeId() == src
-          && edge->getSink()->getNodeId() == sink)
-        continue;
-      ModuloSchedGraphNode *succ =
-          (ModuloSchedGraphNode *) (edge->getSink());
-
-      //if pred is not in the successor set ....
-      bool alreadyInset = false;
-      for (unsigned j = 0; j < succS.size(); j++)
-        if (succS[j]->getNodeId() == succ->getNodeId()) {
-          alreadyInset = true;
-          break;
-        }
-
-      //and not in this set ....
-      for (unsigned j = 0; j < set.size(); j++)
-        if (set[j]->getNodeId() == succ->getNodeId()) {
-          alreadyInset = true;
-          break;
-        }
-
-      //push it into the successor set
-      if (!alreadyInset)
-        succS.push_back(succ);
-    }
-  }
-  return succS;
-}
-
-/*
-  return successor set to the input set
-*/
-
-ModuloSchedGraph::NodeVec ModuloSchedGraph::succSet(NodeVec set){
-
-  return succSet(set, 0, 0);
+#include "llvm/Type.h"
 
+ModuloSchedGraphNode::ModuloSchedGraphNode(unsigned id, int index, 
+					   const Instruction *inst, 
+					   const TargetMachine &targ) 
+  : SchedGraphNodeCommon(id, index), Inst(inst), Target(targ) {
 }
 
-/*
-  return successor set to the input node
-  ignoring any edge between src and sink
-*/
-
-std::vector<ModuloSchedGraphNode*>
-ModuloSchedGraph::succSet(ModuloSchedGraphNode *_node,
-                          unsigned src, unsigned sink){
-
-  std::vector<ModuloSchedGraphNode*>set;
-
-  set.push_back(_node);
-  
-  return succSet(set, src, sink);
-  
+void ModuloSchedGraphNode::print(std::ostream &os) const {
+  os << "Modulo Scheduling Node\n";
 }
 
-/*
-  return successor set to the input node
-*/
-
-std::vector<ModuloSchedGraphNode*>
-ModuloSchedGraph::succSet(ModuloSchedGraphNode * _node){
-  
-  return succSet(_node, 0, 0);
-  
-}
+ModuloSchedGraph::ModuloSchedGraph(const BasicBlock *bb, const TargetMachine &targ) 
+  : SchedGraphCommon(), BB(bb), Target(targ) {
 
+  assert(BB != NULL && "Basic Block is null");
 
-/*
-  find maximum delay between srcId and sinkId
-*/
+  //Builds nodes from each instruction in the basic block
+  buildNodesForBB();
 
-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;
-  
 }
 
-/*
-  dump all circuits found
-*/
-
-void 
-ModuloSchedGraph::dumpCircuits(){
-  
-  DEBUG_PRINT(std::cerr << "dumping circuits for graph:\n");
-  int j = -1;
-  while (circuits[++j][0] != 0) {
-    int k = -1;
-    while (circuits[j][++k] != 0)
-      DEBUG_PRINT(std::cerr << circuits[j][k] << "\t");
-    DEBUG_PRINT(std::cerr << "\n");
+void ModuloSchedGraph::buildNodesForBB() {
+  int count = 0;
+  for (BasicBlock::const_iterator i = BB->begin(), e = BB->end(); i != e; ++i) {
+    addNode(i,new ModuloSchedGraphNode(size(), count, i, Target));
+    count++;
   }
-}
 
-/*
-  dump all sets found
-*/
+	    //Get machine instruction(s) for the llvm instruction
+	    //MachineCodeForInstruction &MC = MachineCodeForInstruction::get(Node->first);
+	    
 
-void 
-ModuloSchedGraph::dumpSet(std::vector < ModuloSchedGraphNode * >set){
-  
-  for (unsigned i = 0; i < set.size(); i++)
-    DEBUG_PRINT(std::cerr << set[i]->getNodeId() << "\t");
-  DEBUG_PRINT(std::cerr << "\n");
-  
 }
 
-/*
-  return union of set1 and set2
-*/
-
-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;
+void ModuloSchedGraph::addNode(const Instruction *I,
+			       ModuloSchedGraphNode *node) {
+  assert(node!= NULL && "New ModuloSchedGraphNode is null");
+  GraphMap[I] = node;
 }
 
-/*
-  return conjuction of set1 and set2
-*/
-std::vector<ModuloSchedGraphNode*>
-ModuloSchedGraph::vectorConj(std::vector<ModuloSchedGraphNode*> set1,
-                             std::vector<ModuloSchedGraphNode*> set2){
+void ModuloSchedGraph::addDepEdges() {
   
-  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;
-
-}
-
-/*
-  return the result of subtracting set2 from set1 
-  (set1 -set2)
-*/
-ModuloSchedGraph::NodeVec 
-ModuloSchedGraph::vectorSub(NodeVec set1,
-			    NodeVec set2){
+  //Get Machine target information for calculating delay
+  const TargetInstrInfo &MTI = Target.getInstrInfo();
   
-  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);
+  //Loop over instruction in BB and gather dependencies
+  for(BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
     
-  }
-  
-  return newVec;
-  
-}
-
-/*
-  order all nodes in the basicblock
-  based on the sets information and node property
-
-  output: ordered nodes are stored in oNodes
-*/
-
-void ModuloSchedGraph::orderNodes() {
-  oNodes.clear();
-
-  std::vector < ModuloSchedGraphNode * >set;
-  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 (ModuloScheduling::printScheduleProcess())
-    DEBUG_PRINT(std::cerr << "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 (ModuloScheduling::printScheduleProcess()) {
-    DEBUG_PRINT(std::cerr << "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 (ModuloScheduling::printScheduleProcess())
-          DEBUG_PRINT(std::cerr << "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 (ModuloScheduling::printScheduleProcess())
-          DEBUG_PRINT(std::cerr << "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 (ModuloScheduling::printScheduleProcess()) {
-      DEBUG_PRINT(std::cerr << "order finished\n");
-      DEBUG_PRINT(std::cerr << "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 (ModuloScheduling::printScheduleProcess())
-      DEBUG_PRINT(std::cerr << "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 (ModuloScheduling::printScheduleProcess())
-        DEBUG_PRINT(std::cerr << "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));
+    //Ignore instructions of the void type
+    if(I->getType() != Type::VoidTy) {
+      
+      //Iterate over def-use chain and add true dependencies
+      for (Value::use_const_iterator U = I->use_begin(), e = I->use_end(); U != e; 
+	   ++U) {
+	if (Instruction *Inst = dyn_cast<Instruction>(*U)) {
+	  //Check if a node already exists for this instruction
+	  ModuloSchedGraph::iterator Sink = find(Inst);
+	  
+	  //If the instruction is in our graph, add appropriate edges
+	  if(Sink->second != NULL) {
+	    //assert if self loop
+	    assert(&*I == Sink->first && "Use edge to itself!");
+	    
+	    //Create edge and set delay equal to node latency
+	    //FIXME: Is it safe to do this?
+	    ModuloSchedGraph::iterator Src = find(I);
+	    SchedGraphEdge *trueDep = new SchedGraphEdge(&*Src->second ,&*Sink->second, &*I,
+							 SchedGraphEdge::TrueDep,
+							 Src->second->getLatency());
+	    //Determine the iteration difference
+	    //FIXME: Will this ever happen?
+	  }
+	}
       }
     }
-    if (ModuloScheduling::printScheduleProcess()) {
-      DEBUG_PRINT(std::cerr << "next set is:\n");
-      dumpSet(set);
-    }
-  }  
-
-}
-
-
-
-/*
-
-  build graph for instructions in this basic block
-
-*/
-void ModuloSchedGraph::buildGraph(const TargetMachine & target)
-{
-  
-  assert(this->bb && "The basicBlock is NULL?");
-  
-  // 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);
-
-  if (ModuloScheduling::printScheduleProcess())
-    this->dump(bb);
-  
-  if (isLoop(bb)) {
-    
-    DEBUG_PRINT(cerr << "building nodes for this BasicBlock\n");
-    buildNodesforBB(target, bb);
     
-    DEBUG_PRINT(cerr << "adding def-use edge to this basic block\n");
-    this->addDefUseEdges(bb);
-
-    DEBUG_PRINT(cerr << "adding CD edges to this basic block\n");
-    this->addCDEdges(bb);
-
-    DEBUG_PRINT(cerr << "adding memory edges to this basicblock\n");
-    this->addMemEdges(bb);
-    
-    int ResII = this->computeResII(bb);
-
-    if (ModuloScheduling::printScheduleProcess())
-      DEBUG_PRINT(std::cerr << "ResII is " << ResII << "\n");
-
-    int RecII = this->computeRecII(bb);
-    if (ModuloScheduling::printScheduleProcess())
-      DEBUG_PRINT(std::cerr << "RecII is " << RecII << "\n");
-    
-    this->MII = std::max(ResII, RecII);
-
-    this->computeNodeProperty(bb);
-    if (ModuloScheduling::printScheduleProcess())
-      this->dumpNodeProperty();
-
-    this->orderNodes();
-    
-    if (ModuloScheduling::printScheduleProcess())
-      this->dump();
-
   }
-}
-
-/*
-  get node with nodeId
-*/
-
-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;
-  
-}
-
-/*
-  compute RecurrenceII
-*/
-
-int 
-ModuloSchedGraph::computeRecII(const BasicBlock *bb){
-
-  int RecII = 0;
-
-
-  //FIXME: only deal with circuits starting at the first node: the phi node
-  //nodeId=2;
-
-  //search all elementary circuits in the dependence 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
-  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();
-    // DEBUG_PRINT(std::cerr<<"current node is "<<currentNodeId<<"\n");
-
-    ModuloSchedGraphNode *nextNode = NULL;
-    for (ModuloSchedGraphNode::const_iterator I =
-         currentNode->beginOutEdges(), E = currentNode->endOutEdges();
-         I != E; I++) {
-      //DEBUG_PRINT(std::cerr <<" searching in outgoint edges of node
-      //"<<currentNodeId<<"\n";
-      unsigned nodeId = ((SchedGraphEdge *) * I)->getSink()->getNodeId();
-      bool inpath = false, instack = false;
-      int k;
-
-      //DEBUG_PRINT(std::cerr<<"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) {
-      //DEBUG_PRINT(std::cerr<<"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 {
-      //DEBUG_PRINT(std::cerr<<"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 (ModuloScheduling::printScheduleProcess())
-        DEBUG_PRINT(std::cerr << "circuits found are:\n");
-      int j = -1;
-      while (circuits[++j][0] != 0) {
-        int k = -1;
-        while (circuits[j][++k] != 0)
-          if (ModuloScheduling::printScheduleProcess())
-            DEBUG_PRINT(std::cerr << circuits[j][k] << "\t");
-        if (ModuloScheduling::printScheduleProcess())
-          DEBUG_PRINT(std::cerr << "\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];
-
-          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 (ModuloScheduling::printScheduleProcess())
-          DEBUG_PRINT(std::cerr << "The total Delay in the circuit is " << sumDelay
-                << "\n");
-
-        RecII = RecII > sumDelay ? RecII : sumDelay;
-
-      }
-      return RecII;
-    }
-
-  }
-
-  return -1;
-}
-
-/*
-  update resource usage vector (ruVec)
-*/
-void 
-ModuloSchedGraph::addResourceUsage(std::vector<std::pair<int,int> > &ruVec,
-				   int rid){
   
-  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));
-
 }
 
-/*
-  dump the resource usage vector
-*/
-
-void 
-ModuloSchedGraph::dumpResourceUsage(std::vector<std::pair<int,int> > &ru){
-
-  TargetSchedInfo & msi = (TargetSchedInfo &) target.getSchedInfo();
-  
-  std::vector<std::pair<int,int> > resourceNumVector = msi.resourceNumVector;
-  DEBUG_PRINT(std::cerr << "resourceID\t" << "resourceNum\n");
-  for (unsigned i = 0; i < resourceNumVector.size(); i++)
-    DEBUG_PRINT(std::cerr << resourceNumVector[i].
-        first << "\t" << resourceNumVector[i].second << "\n");
+void ModuloSchedGraph::ASAP() {
 
-  DEBUG_PRINT(std::cerr << " maxNumIssueTotal(issue slot in one cycle) = " << msi.
-        maxNumIssueTotal << "\n");
-  DEBUG_PRINT(std::cerr << "resourceID\t resourceUsage\t ResourceNum\n");
-  for (unsigned i = 0; i < ru.size(); i++) {
-    DEBUG_PRINT(std::cerr << ru[i].first << "\t" << ru[i].second);
-    const unsigned resNum = msi.getCPUResourceNum(ru[i].first);
-    DEBUG_PRINT(std::cerr << "\t" << resNum << "\n");
 
-  }  
 }
 
-/*
-  compute thre resource restriction II
-*/
+void ModuloSchedGraph::ALAP() {
 
-int 
-ModuloSchedGraph::computeResII(const BasicBlock * bb){
-  
-  const TargetInstrInfo & mii = target.getInstrInfo();
-  const TargetSchedInfo & msi = target.getSchedInfo();
-  
-  int ResII;
-  std::vector<std::pair<int,int> > resourceUsage;
-
-  for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); I != E;
-       I++) {
-    if (ModuloScheduling::printScheduleProcess()) {
-      DEBUG_PRINT(std::cerr << "machine instruction for llvm instruction( node " <<
-            getGraphNodeForInst(I)->getNodeId() << ")\n");
-      DEBUG_PRINT(std::cerr << "\t" << *I);
-    }
-    MachineCodeForInstruction & tempMvec =
-        MachineCodeForInstruction::get(I);
-    if (ModuloScheduling::printScheduleProcess())
-      DEBUG_PRINT(std::cerr << "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 (ModuloScheduling::printScheduleProcess())
-        DEBUG_PRINT(std::cerr << "resources Usage for this Instr(totCycles="
-              << totCycles << ",mindLatency="
-              << mii.minLatency(minstr->getOpCode()) << "): " << *minstr
-              << "\n");
-      for (unsigned j = 0; j < resources.size(); j++) {
-        if (ModuloScheduling::printScheduleProcess())
-          DEBUG_PRINT(std::cerr << "cycle " << j << ": ");
-        for (unsigned k = 0; k < resources[j].size(); k++) {
-          if (ModuloScheduling::printScheduleProcess())
-            DEBUG_PRINT(std::cerr << "\t" << resources[j][k]);
-          addResourceUsage(resourceUsage, resources[j][k]);
-        }
-        if (ModuloScheduling::printScheduleProcess())
-          DEBUG_PRINT(std::cerr << "\n");
-      }
-    }
-  }
-  if (ModuloScheduling::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 = std::max((int) tempII, ResII);
-  }
-  return ResII;
 }
 
+void ModuloSchedGraph::MOB() {
 
-
-/*
-  dump the basicblock
-*/
-
-void 
-ModuloSchedGraph::dump(const BasicBlock * bb){
-  
-  DEBUG_PRINT(std::cerr << "dumping basic block:");
-  DEBUG_PRINT(std::cerr << (bb->hasName()? bb->getName() : "block")
-	      << " (" << bb << ")" << "\n");
-  
 }
 
-/*
-  dump the basicblock to ostream os
-*/
+void ModuloSchedGraph::ComputeDepth() {
 
-void 
-ModuloSchedGraph::dump(const BasicBlock * bb, std::ostream & os){
-
-  os << "dumping basic block:";
-  os << (bb->hasName()? bb->getName() : "block")
-      << " (" << bb << ")" << "\n";
 }
 
-/*
-  dump the graph
-*/
-
-void ModuloSchedGraph::dump() const
-{
-  DEBUG_PRINT(std::cerr << " ModuloSchedGraph for basic Blocks:");
-
-  DEBUG_PRINT(std::cerr << (bb->hasName()? bb->getName() : "block")
-	<< " (" << bb << ")" <<  "");
-
-  DEBUG_PRINT(std::cerr << "\n\n    Actual Root nodes : ");
-  for (unsigned i = 0, N = graphRoot->outEdges.size(); i < N; i++)
-    DEBUG_PRINT(std::cerr << graphRoot->outEdges[i]->getSink()->getNodeId()
-          << ((i == N - 1) ? "" : ", "));
-
-  DEBUG_PRINT(std::cerr << "\n    Graph Nodes:\n");
+void  ModuloSchedGraph::ComputeHeight() {
 
-  unsigned numNodes = bb->size();
-  for (unsigned i = 2; i < numNodes + 2; i++) {
-    ModuloSchedGraphNode *node = getNode(i);
-    DEBUG_PRINT(std::cerr << "\n" << *node);
-  }
-
-  DEBUG_PRINT(std::cerr << "\n");
 }
 
-
-/*
-  dump all node property
-*/
-
-void ModuloSchedGraph::dumpNodeProperty() const
-{
-
-  unsigned numNodes = bb->size();
-  for (unsigned i = 2; i < numNodes + 2; i++) {
-    ModuloSchedGraphNode *node = getNode(i);
-    DEBUG_PRINT(std::cerr << "NodeId " << node->getNodeId() << "\t");
-    DEBUG_PRINT(std::cerr << "ASAP " << node->getASAP() << "\t");
-    DEBUG_PRINT(std::cerr << "ALAP " << node->getALAP() << "\t");
-    DEBUG_PRINT(std::cerr << "mov " << node->getMov() << "\t");
-    DEBUG_PRINT(std::cerr << "depth " << node->getDepth() << "\t");
-    DEBUG_PRINT(std::cerr << "height " << node->getHeight() << "\t\n");
-  }
+void ModuloSchedGraphSet::addGraph(ModuloSchedGraph *graph) {
+  assert(graph!=NULL && "Graph for BasicBlock is null");
+  Graphs.push_back(graph);
 }
 
 
+ModuloSchedGraphSet::ModuloSchedGraphSet(const Function *F, 
+					 const TargetMachine &targ) 
+  : function(F) {
 
-
-/************member functions for ModuloSchedGraphSet**************/
-
-/*
-  constructor
-*/
-
-ModuloSchedGraphSet::ModuloSchedGraphSet(const Function *function,
-                                         const TargetMachine &target)
-:  method(function){
-  
-  buildGraphsForMethod(method, target);
-
+  //Create graph for each BB in this function
+  for (Function::const_iterator BI = F->begin(); BI != F->end(); ++BI)
+    addGraph(new ModuloSchedGraph(BI, targ));
 }
 
-/*
-  destructor
-*/
-
-
 ModuloSchedGraphSet::~ModuloSchedGraphSet(){
   
   //delete all the graphs
-  for (iterator I = begin(), E = end(); I != E; ++I)
-    delete *I;
 }
 
-
-
-/*
-  build graph for each basicblock in this method
-*/
-
-void 
-ModuloSchedGraphSet::buildGraphsForMethod(const Function *F,
-					  const TargetMachine &target){
-  
-  for (Function::const_iterator BI = F->begin(); BI != F->end(); ++BI){
-    const BasicBlock* local_bb;
-    
-    local_bb=BI;
-    addGraph(new ModuloSchedGraph((BasicBlock*)local_bb, target));
-  }
-  
-}
-
-/*
-  dump the graph set
-*/
-
-void 
-ModuloSchedGraphSet::dump() const{
-  
-  DEBUG_PRINT(std::cerr << " ====== ModuloSched graphs for function `" << 
-	      method->getName() << "' =========\n\n");
-  for (const_iterator I = begin(); I != end(); ++I)
-    (*I)->dump();
-  
-  DEBUG_PRINT(std::cerr << "\n=========End graphs for function `" << method->getName()
-	      << "' ==========\n\n");
-}
-
-
-
-
-/********************misc functions***************************/
-
-
-/*
-  dump the input basic block
-*/
-
-static void 
-dumpBasicBlock(const BasicBlock * bb){
-  
-  DEBUG_PRINT(std::cerr << "dumping basic block:");
-  DEBUG_PRINT(std::cerr << (bb->hasName()? bb->getName() : "block")
-	      << " (" << bb << ")" << "\n");
-}
-
-/*
-  dump the input node
-*/
-
-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;
-}
diff --git a/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h b/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h
index 2abd448fcd..3404a747ee 100644
--- a/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h
+++ b/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h
@@ -1,367 +1,101 @@
 //===- ModuloSchedGraph.h - Modulo Scheduling Graph and Set -*- C++ -*-----===//
-//
-// This header defines the primative classes that make up a data structure
-// graph.
+// 
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_CODEGEN_MODULO_SCHED_GRAPH_H
-#define LLVM_CODEGEN_MODULO_SCHED_GRAPH_H
+#ifndef LLVM_MODULO_SCHED_GRAPH_H
+#define LLVM_MODULO_SCHED_GRAPH_H
 
 #include "llvm/Instruction.h"
+#include "llvm/CodeGen/SchedGraphCommon.h"
 #include "llvm/Target/TargetMachine.h"
-#include "llvm/Target/TargetInstrInfo.h"
-#include "Support/GraphTraits.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Function.h"
 #include "Support/hash_map"
-#include "../InstrSched/SchedGraphCommon.h"
-#include <iostream>
+#include <vector>
 
-//===----------------------------------------------------------------------===//
-// ModuloSchedGraphNode - Implement a data structure based on the
-// SchedGraphNodeCommon this class stores informtion needed later to order the
-// nodes in modulo scheduling
-//
-class ModuloSchedGraphNode:public SchedGraphNodeCommon {
-private:
-  // the corresponding instruction 
-  const Instruction *inst;
 
-  // whether this node's property(ASAP,ALAP, ...) has been computed
-  bool propertyComputed;
+class ModuloSchedGraphNode : public SchedGraphNodeCommon {
 
-  // ASAP: the earliest time the node could be scheduled
-  // ALAP: the latest time the node couldbe scheduled
-  // depth: the depth of the node
-  // height: the height of the node
-  // mov: the mobility function, computed as ALAP - ASAP
-  // scheTime: the scheduled time if this node has been scheduled 
-  // earlyStart: the earliest time to be tried to schedule the node
-  // lateStart: the latest time to be tried to schedule the node
-  int ASAP, ALAP, depth, height, mov;
-  int schTime;
-  int earlyStart, lateStart;
+  const Instruction *Inst;  //Node's Instruction
+  unsigned Earliest;        //ASAP, or earliest time to be scheduled
+  unsigned Latest;          //ALAP, or latested time to be scheduled
+  unsigned Depth;           //Max Distance from node to the root
+  unsigned Height;          //Max Distance from node to leaf
+  unsigned Mobility;        //MOB, number of time slots it can be scheduled
+  const TargetMachine &Target; //Target information.
 
 public:
-
-  //get the instruction
-  const Instruction *getInst() const {
-    return inst;
-  }
-  //get the instruction op-code name
-  const char *getInstOpcodeName() const {
-    return inst->getOpcodeName();
-  }
-  //get the instruction op-code
-  const unsigned getInstOpcode() const {
-    return inst->getOpcode();
-  }
-
-  //return whether the node is NULL
-  bool isNullNode() const {
-    return (inst == NULL);
-  }
-  //return whether the property of the node has been computed
-  bool getPropertyComputed() {
-    return propertyComputed;
-  }
-  //set the propertyComputed
-  void setPropertyComputed(bool _propertyComputed) {
-    propertyComputed = _propertyComputed;
-  }
+  ModuloSchedGraphNode(unsigned ID, int index, const Instruction *inst, 
+		       const TargetMachine &target);
   
-  //get the corresponding property
-  int getASAP() {
-    return ASAP;
-  }
-  int getALAP() {
-    return ALAP;
-  }
-  int getMov() {
-    return mov;
-  }
-  int getDepth() {
-    return depth;
-  }
-  int getHeight() {
-    return height;
-  }
-  int getSchTime() {
-    return schTime;
-  }
-  int getEarlyStart() {
-    return earlyStart;
-  }
-  int getLateStart() {
-    return lateStart;
-  }
-  void setEarlyStart(int _earlyStart) {
-    earlyStart = _earlyStart;
-  }
-  void setLateStart(int _lateStart) {
-    lateStart = _lateStart;
-  }
-  void setSchTime(int _time) {
-    schTime = _time;
-  }
-
-private:
-  friend class ModuloSchedGraph;
-  friend class SchedGraphNode;
-
-  //constructor:
-  //nodeId: the node id, unique within the each BasicBlock
-  //_bb: which BasicBlock the corresponding instruction belongs to 
-  //_inst: the corresponding instruction
-  //indexInBB: the corresponding instruction's index in the BasicBlock
-  //target: the targetMachine
-  ModuloSchedGraphNode(unsigned int _nodeId,
-                       const BasicBlock * _bb,
-                       const Instruction * _inst,
-                       int indexInBB, const TargetMachine &target);
-
+  void print(std::ostream &os) const;
+  const Instruction* getInst() { return Inst; }
+  unsigned getEarliest() { return Earliest; }
+  unsigned getLatest() { return Latest; }
+  unsigned getDepth() { return Depth; }
+  unsigned getHeight() { return Height; }
+  unsigned getMobility() { return Mobility; }
   
-  friend std::ostream & operator<<(std::ostream & os,
-                                   const ModuloSchedGraphNode & edge);
-
-};
-
-//FIXME: these two value should not be used
-#define MAXNODE 100
-#define MAXCC   100
-
-//===----------------------------------------------------------------------===//
-/// ModuloSchedGraph- the data structure to store dependence between nodes
-/// it catches data dependence and constrol dependence
-/// 
-class ModuloSchedGraph :
-  public SchedGraphCommon,
-  protected hash_map<const Instruction*,ModuloSchedGraphNode*> {
-
-private:
-
-  BasicBlock* bb;
-  
-  //iteration Interval
-  int MII;
-
-  //target machine
-  const TargetMachine & target;
+  void setEarliest(unsigned early) { Earliest = early; }
+  void setLatest(unsigned late) { Latest = late; }
+  void setDepth(unsigned depth) { Depth = depth; }
+  void setHeight(unsigned height) { Height = height; }
+  void setMobility(unsigned mob) { Mobility = mob; }
 
-  //the circuits in the dependence graph
-  unsigned circuits[MAXCC][MAXNODE];
 
-  //the order nodes
-  std::vector<ModuloSchedGraphNode*> oNodes;
-
-  typedef std::vector<ModuloSchedGraphNode*> NodeVec;
-
-  //the function to compute properties
-  void computeNodeASAP(const BasicBlock * in_bb);
-  void computeNodeALAP(const BasicBlock * in_bb);
-  void computeNodeMov(const BasicBlock *  in_bb);
-  void computeNodeDepth(const BasicBlock * in_bb);
-  void computeNodeHeight(const BasicBlock * in_bb);
-
-  //the function to compute node property
-  void computeNodeProperty(const BasicBlock * in_bb);
-
-  //the function to sort nodes
-  void orderNodes();
-
-  //add the resource usage 
-void addResourceUsage(std::vector<std::pair<int,int> > &, int);
-
-  //debug functions:
-  //dump circuits
-  void dumpCircuits();
-  //dump the input set of nodes
-  void dumpSet(std::vector<ModuloSchedGraphNode*> set);
-  //dump the input resource usage table  
-  void dumpResourceUsage(std::vector<std::pair<int,int> > &);
-
-public:
-  //help functions
-
-  //get the maxium the delay between two nodes
-  SchedGraphEdge *getMaxDelayEdge(unsigned srcId, unsigned sinkId);
-
-  //FIXME:
-  //get the predessor Set of the set
-  NodeVec predSet(NodeVec set, unsigned, unsigned);
-  NodeVec predSet(NodeVec set);
-
-  //get the predessor set of the node
-  NodeVec predSet(ModuloSchedGraphNode *node, unsigned, unsigned);
-  NodeVec predSet(ModuloSchedGraphNode *node);
-
-  //get the successor set of the set
-  NodeVec succSet(NodeVec set, unsigned, unsigned);
-  NodeVec succSet(NodeVec set);
-
-  //get the succssor set of the node
-  NodeVec succSet(ModuloSchedGraphNode *node, unsigned, unsigned);
-  NodeVec succSet(ModuloSchedGraphNode *node);
+};
 
-  //return the uniton of the two vectors
-  NodeVec vectorUnion(NodeVec set1, NodeVec set2);
+class ModuloSchedGraph : public SchedGraphCommon {
   
-  //return the consjuction of the two vectors
-  NodeVec vectorConj(NodeVec set1, NodeVec set2);
-
-  //return all nodes in  set1 but not  set2
-  NodeVec vectorSub(NodeVec set1, NodeVec set2);
-
-  typedef hash_map<const Instruction*,ModuloSchedGraphNode*> map_base;
+  const BasicBlock *BB; //The Basic block this graph represents
+  const TargetMachine &Target;
+  hash_map<const Instruction*, ModuloSchedGraphNode*> GraphMap;
 
-public:
-  using map_base::iterator;
-  using map_base::const_iterator;
-
-public:
-
-  //get target machine
-  const TargetMachine & getTarget() {
-    return target;
-  }
-
-  //get the basic block
-  BasicBlock* getBasicBlock() const {
-    return bb;
-  }
-
-
-  //get the iteration interval
-  const int getMII() {
-    return MII;
-  }
-
-  //get the ordered nodes
-  const NodeVec & getONodes() {
-    return oNodes;
-  }
-
-  //get the number of nodes (including the root and leaf)
-  //note: actually root and leaf is not used
-  const unsigned int getNumNodes() const {
-    return size() + 2;
-  }
-
-  //return wether the BasicBlock 'bb' contains a loop
-  bool isLoop(const BasicBlock *bb);
-
-  //return the node for the input instruction
-  ModuloSchedGraphNode *getGraphNodeForInst(const Instruction *inst) const {
-    const_iterator onePair = this->find(inst);
-    return (onePair != this->end()) ? (*onePair).second : NULL;
-  }
-
-  // Debugging support
-  //dump the graph
-  void dump() const;
-
-  // dump the basicBlock
-  void dump(const BasicBlock *bb);
-
-  //dump the basicBlock into 'os' stream
-  void dump(const BasicBlock *bb, std::ostream &os);
-
-  //dump the node property
-  void dumpNodeProperty() const;
-  
-private:
-  friend class ModuloSchedGraphSet;     //give access to ctor
+  void buildNodesForBB();
 
 public:
-  ModuloSchedGraph(BasicBlock * in_bb, 
-		   const TargetMachine & in_target)
-    :SchedGraphCommon(), bb(in_bb),target(in_target)
-  {
-    buildGraph(target);
-  }
-
-  ~ModuloSchedGraph() {
-    for (const_iterator I = begin(); I != end(); ++I)
-      delete I->second;
-  }
-
-  // Unorder iterators
-  // return values are pair<const Instruction*, ModuloSchedGraphNode*>
-  using map_base::begin;
-  using map_base::end;
-
-  void addHash(const Instruction *inst,
-	       ModuloSchedGraphNode *node){
-    
-    assert((*this)[inst] == NULL);
-    (*this)[inst] = node;
-    
-  }
-
-  // Graph builder
-  ModuloSchedGraphNode *getNode(const unsigned nodeId) const;
-
-  // Build the graph from the basicBlock
-  void buildGraph(const TargetMachine &target);
-
-  // Build nodes for BasicBlock
-  void buildNodesforBB(const TargetMachine &target,
-                       const BasicBlock *bb);
-
-  //find definitiona and use information for all nodes
-  void findDefUseInfoAtInstr(const TargetMachine &target,
-                             ModuloSchedGraphNode *node,
-                             NodeVec &memNode,
-                             RegToRefVecMap &regToRefVecMap,
-                             ValueToDefVecMap &valueToDefVecMap);
-
-  //add def-use edge
-  void addDefUseEdges(const BasicBlock *bb);
-
-  //add control dependence edges
-  void addCDEdges(const BasicBlock *bb);
-
-  //add memory dependence dges
-  void addMemEdges(const BasicBlock *bb);
-
-  //computer source restrictoin II
-  int computeResII(const BasicBlock *bb);
-
-  //computer recurrence II
-  int computeRecII(const BasicBlock *bb);
+  typedef hash_map<const Instruction*, 
+		   ModuloSchedGraphNode*>::iterator iterator;
+  typedef hash_map<const Instruction*, 
+		   ModuloSchedGraphNode*>::const_iterator const_iterator;
+
+
+  ModuloSchedGraph(const BasicBlock *bb, const TargetMachine &targ);
+
+  const BasicBlock* getBB() { return BB; }
+  void setBB(BasicBlock *bb) { BB = bb; }
+  unsigned size() { return GraphMap.size(); }
+  void addNode(const Instruction *I, ModuloSchedGraphNode *node);
+  void ASAP(); //Calculate earliest schedule time for all nodes in graph.
+  void ALAP(); //Calculate latest schedule time for all nodes in graph.
+  void MOB(); //Calculate mobility for all nodes in the graph.
+  void ComputeDepth(); //Compute depth of each node in graph
+  void ComputeHeight(); //Computer height of each node in graph
+  void addDepEdges(); //Add Dependencies
+  iterator find(const Instruction *I) { return GraphMap.find(I); }
 };
 
-//==================================-
-// Graph set
 
-class ModuloSchedGraphSet : public std::vector<ModuloSchedGraph*> {
-private:
-  const Function *method;
-
-public:
-  typedef std::vector<ModuloSchedGraph*> baseVector;
-  using baseVector::iterator;
-  using baseVector::const_iterator;
+class ModuloSchedGraphSet {
+  
+  const Function *function; //Function this set of graphs represent.
+  std::vector<ModuloSchedGraph*> Graphs;
 
 public:
-  ModuloSchedGraphSet(const Function *function, const TargetMachine &target);
+  typedef std::vector<ModuloSchedGraph*>::iterator iterator;
+  typedef std::vector<ModuloSchedGraph*>::const_iterator const_iterator;
+ 
+  iterator begin() { return Graphs.begin(); }
+  iterator end() { return Graphs.end(); }
+ 
+  ModuloSchedGraphSet(const Function *func, const TargetMachine &target);
   ~ModuloSchedGraphSet();
 
-  // Iterators
-  using baseVector::begin;
-  using baseVector::end;
-
-  // Debugging support
+  void addGraph(ModuloSchedGraph *graph);
   void dump() const;
 
-private:
-  void addGraph(ModuloSchedGraph *graph) {
-    assert(graph != NULL);
-    this->push_back(graph);
-  }
 
-  // Graph builder
-  void buildGraphsForMethod(const Function *F,
-                            const TargetMachine &target);
 };
 
 #endif
diff --git a/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp b/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp
index 49f4246c02..bad3e97e48 100644
--- a/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp
+++ b/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp
@@ -1,983 +1,35 @@
-//===- ModuloScheduling.cpp - Modulo Software Pipelining ------------------===//
+//===-- ModuloScheduling.cpp - Software Pipeling Approach - SMS --*- C++ -*--=//
 //
-// Implements the llvm/CodeGen/ModuloScheduling.h interface
+// The is a software pipelining pass based on the Swing Modulo Scheduling
+// alogrithm (SMS).
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/BasicBlock.h"
-#include "llvm/Constants.h"
-#include "llvm/iTerminators.h"
-#include "llvm/iPHINode.h"
-#include "llvm/CodeGen/MachineInstr.h"
-#include "llvm/CodeGen/MachineCodeForInstruction.h"
-#include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/CodeGen/InstrSelection.h"
-#include "llvm/Target/TargetSchedInfo.h"
-#include "llvm/Target/TargetMachine.h"
-#include "Support/CommandLine.h"
-#include "Support/Statistic.h"
 #include "ModuloSchedGraph.h"
-#include "ModuloScheduling.h"
-#include <algorithm>
-#include <fstream>
 
-//************************************************************
-// printing Debug information
-// ModuloSchedDebugLevel stores the value of debug level
-// modsched_os is the ostream to dump debug information, which is written into
-// the file 'moduloSchedDebugInfo.output'
-// see ModuloSchedulingPass::runOnFunction()
-//************************************************************
+#include "llvm/Pass.h"
+#include "llvm/Function.h"
 
-ModuloSchedDebugLevel_t ModuloSchedDebugLevel;
-
-cl::opt<ModuloSchedDebugLevel_t,true>
-SDL_opt("modsched", cl::Hidden, cl::location(ModuloSchedDebugLevel),
-	cl::desc("enable modulo scheduling debugging information"),
-	cl::values(clEnumValN(ModuloSchedDebugLevel_NoDebugInfo,
-			      "none", "disable debug output"),
-		   clEnumValN(ModuloSchedDebugLevel_PrintSchedule,
-			      "psched", "print original and new schedule"),
-		   clEnumValN(ModuloSchedDebugLevel_PrintScheduleProcess,
-			      "pschedproc",
-			      "print how the new schdule is produced"),
-		   0));
-
-// Computes the schedule and inserts epilogue and prologue
-//
-void 
-ModuloScheduling::instrScheduling(){
-
-
-  if (ModuloScheduling::printScheduleProcess())
-    DEBUG_PRINT(std::cerr << "************ computing modulo schedule ***********\n");
-
-  const TargetSchedInfo & msi = target.getSchedInfo();
-
-  //number of issue slots in the in each cycle
-  int numIssueSlots = msi.maxNumIssueTotal;
-
-  //compute the schedule
-  bool success = false;
-  while (!success) {
-    //clear memory from the last round and initialize if necessary
-    clearInitMem(msi);
-
-    //compute schedule and coreSchedule with the current II
-    success = computeSchedule();
-
-    if (!success) {
-      II++;
-      if (ModuloScheduling::printScheduleProcess())
-        DEBUG_PRINT(std::cerr << "increase II  to " << II << "\n");
-    }
-  }
-
-  //print the final schedule
-  dumpFinalSchedule();
-  
-  //the schedule has been computed
-  //create epilogue, prologue and kernel BasicBlock
-
-  //find the successor for this BasicBlock
-  BasicBlock *succ_bb = getSuccBB(bb);
-
-  //print the original BasicBlock if necessary
-  if (ModuloScheduling::printSchedule()) {
-    DEBUG_PRINT(std::cerr << "dumping the orginal block\n");
-    graph.dump(bb);
-  }
-  //construction of prologue, kernel and epilogue
-  
-  /*
-  BasicBlock *kernel = bb->splitBasicBlock(bb->begin());
-  BasicBlock *prologue = bb;
-  BasicBlock *epilogue = kernel->splitBasicBlock(kernel->begin());
-  */
-
-  // Construct prologue
-  /*constructPrologue(prologue);*/
-
-  // Construct kernel
-  
-  /*constructKernel(prologue, kernel, epilogue);*/
-
-  // Construct epilogue
-
-  /*constructEpilogue(epilogue, succ_bb);*/
+namespace {
   
-  //print the BasicBlocks if necessary
-//    if (0){
-//      DEBUG_PRINT(std::cerr << "dumping the prologue block:\n");
-//      graph.dump(prologue);
-//      DEBUG_PRINT(std::cerr << "dumping the kernel block\n");
-//      graph.dump(kernel);
-//      DEBUG_PRINT(std::cerr << "dumping the epilogue block\n");
-//      graph.dump(epilogue);
-//    }
-
-}
-
-
-// Clear memory from the last round and initialize if necessary
-//
-
-void 
-ModuloScheduling::clearInitMem(const TargetSchedInfo & msi){
-
-  unsigned numIssueSlots = msi.maxNumIssueTotal;
-  // clear nodeScheduled from the last round
-  if (ModuloScheduling::printScheduleProcess()) {
-    DEBUG_PRINT(std::cerr << "***** new round  with II= " << II << " ***********\n");
-    DEBUG_PRINT(std::cerr <<
-        " ************clear the vector nodeScheduled*************\n");
-  }
-  nodeScheduled.clear();
-
-  // clear resourceTable from the last round and reset it 
-  resourceTable.clear();
-  for (unsigned i = 0; i < II; ++i)
-    resourceTable.push_back(msi.resourceNumVector);
-
-  // clear the schdule and coreSchedule from the last round 
-  schedule.clear();
-  coreSchedule.clear();
-
-  // create a coreSchedule of size II*numIssueSlots
-  // each entry is NULL
-  while (coreSchedule.size() < II) {
-    std::vector < ModuloSchedGraphNode * >*newCycle =
-        new std::vector < ModuloSchedGraphNode * >();
-    for (unsigned k = 0; k < numIssueSlots; ++k)
-      newCycle->push_back(NULL);
-    coreSchedule.push_back(*newCycle);
-  }
-}
-
-// Compute schedule and coreSchedule with the current II
-//
-bool 
-ModuloScheduling::computeSchedule(){
-
-
-  if (ModuloScheduling::printScheduleProcess())
-    DEBUG_PRINT(std::cerr << "start to compute schedule\n");
-
-  // Loop over the ordered nodes
-  for (NodeVec::const_iterator I = oNodes.begin(); I != oNodes.end(); ++I) {
-    // Try to schedule for node I
-    if (ModuloScheduling::printScheduleProcess())
-      dumpScheduling();
-    ModuloSchedGraphNode *node = *I;
-
-    // Compute whether this node has successor(s)
-    bool succ = true;
-
-    // Compute whether this node has predessor(s)
-    bool pred = true;
-
-    NodeVec schSucc = graph.vectorConj(nodeScheduled, graph.succSet(node));
-    if (schSucc.empty())
-      succ = false;
-    NodeVec schPred = graph.vectorConj(nodeScheduled, graph.predSet(node));
-    if (schPred.empty())
-      pred = false;
-
-    //startTime: the earliest time we will try to schedule this node
-    //endTime: the latest time we will try to schedule this node
-    int startTime, endTime;
-
-    //node's earlyStart: possible earliest time to schedule this node
-    //node's lateStart: possible latest time to schedule this node
-    node->setEarlyStart(-1);
-    node->setLateStart(9999);
-
-    //this node has predessor but no successor
-    if (!succ && pred) {
-      // This node's earlyStart is it's predessor's schedule time + the edge
-      // delay - the iteration difference* II
-      for (unsigned i = 0; i < schPred.size(); i++) {
-        ModuloSchedGraphNode *predNode = schPred[i];
-        SchedGraphEdge *edge =
-            graph.getMaxDelayEdge(predNode->getNodeId(),
-                                  node->getNodeId());
-        int temp =
-            predNode->getSchTime() + edge->getMinDelay() -
-            edge->getIteDiff() * II;
-        node->setEarlyStart(std::max(node->getEarlyStart(), temp));
-      }
-      startTime = node->getEarlyStart();
-      endTime = node->getEarlyStart() + II - 1;
-    }
-    // This node has a successor but no predecessor
-    if (succ && !pred) {
-      for (unsigned i = 0; i < schSucc.size(); ++i) {
-        ModuloSchedGraphNode *succNode = schSucc[i];
-        SchedGraphEdge *edge =
-            graph.getMaxDelayEdge(succNode->getNodeId(),
-                                  node->getNodeId());
-        int temp =
-            succNode->getSchTime() - edge->getMinDelay() +
-            edge->getIteDiff() * II;
-        node->setLateStart(std::min(node->getEarlyStart(), temp));
-      }
-      startTime = node->getLateStart() - II + 1;
-      endTime = node->getLateStart();
-    }
-    // This node has both successors and predecessors
-    if (succ && pred) {
-      for (unsigned i = 0; i < schPred.size(); ++i) {
-        ModuloSchedGraphNode *predNode = schPred[i];
-        SchedGraphEdge *edge =
-            graph.getMaxDelayEdge(predNode->getNodeId(),
-                                  node->getNodeId());
-        int temp =
-            predNode->getSchTime() + edge->getMinDelay() -
-            edge->getIteDiff() * II;
-        node->setEarlyStart(std::max(node->getEarlyStart(), temp));
-      }
-      for (unsigned i = 0; i < schSucc.size(); ++i) {
-        ModuloSchedGraphNode *succNode = schSucc[i];
-        SchedGraphEdge *edge =
-            graph.getMaxDelayEdge(succNode->getNodeId(),
-                                  node->getNodeId());
-        int temp =
-            succNode->getSchTime() - edge->getMinDelay() +
-            edge->getIteDiff() * II;
-        node->setLateStart(std::min(node->getEarlyStart(), temp));
-      }
-      startTime = node->getEarlyStart();
-      endTime = std::min(node->getLateStart(),
-                         node->getEarlyStart() + ((int) II) - 1);
-    }
-    //this node has no successor or predessor
-    if (!succ && !pred) {
-      node->setEarlyStart(node->getASAP());
-      startTime = node->getEarlyStart();
-      endTime = node->getEarlyStart() + II - 1;
-    }
-    //try to schedule this node based on the startTime and endTime
-    if (ModuloScheduling::printScheduleProcess())
-      DEBUG_PRINT(std::cerr << "scheduling the node " << (*I)->getNodeId() << "\n");
-
-    bool success =
-        this->ScheduleNode(node, startTime, endTime, nodeScheduled);
-    if (!success)
-      return false;
-  }
-  return true;
-}
-
-
-// Get the successor of the BasicBlock
-//
-BasicBlock *
-ModuloScheduling::getSuccBB(BasicBlock *bb){
-
-  BasicBlock *succ_bb;
-  for (unsigned i = 0; i < II; ++i)
-    for (unsigned j = 0; j < coreSchedule[i].size(); ++j)
-      if (coreSchedule[i][j]) {
-        const Instruction *ist = coreSchedule[i][j]->getInst();
-
-        //we can get successor from the BranchInst instruction
-        //assume we only have one successor (besides itself) here
-        if (BranchInst::classof(ist)) {
-          BranchInst *bi = (BranchInst *) ist;
-          assert(bi->isConditional() &&
-                 "the branchInst is not a conditional one");
-          assert(bi->getNumSuccessors() == 2
-                 && " more than two successors?");
-          BasicBlock *bb1 = bi->getSuccessor(0);
-          BasicBlock *bb2 = bi->getSuccessor(1);
-          assert((bb1 == bb || bb2 == bb) &&
-                 " None of its successors is itself?");
-          if (bb1 == bb)
-            succ_bb = bb2;
-          else
-            succ_bb = bb1;
-          return succ_bb;
-        }
-      }
-  assert(0 && "NO Successor?");
-  return NULL;
-}
-
-
-// Get the predecessor of the BasicBlock
-//
-BasicBlock *
-ModuloScheduling::getPredBB(BasicBlock *bb){
-
-  BasicBlock *pred_bb;
-  for (unsigned i = 0; i < II; ++i)
-    for (unsigned j = 0; j < coreSchedule[i].size(); ++j)
-      if (coreSchedule[i][j]) {
-        const Instruction *ist = coreSchedule[i][j]->getInst();
-
-        //we can get predecessor from the PHINode instruction
-        //assume we only have one predecessor (besides itself) here
-        if (PHINode::classof(ist)) {
-          PHINode *phi = (PHINode *) ist;
-          assert(phi->getNumIncomingValues() == 2 &&
-                 " the number of incoming value is not equal to two? ");
-          BasicBlock *bb1 = phi->getIncomingBlock(0);
-          BasicBlock *bb2 = phi->getIncomingBlock(1);
-          assert((bb1 == bb || bb2 == bb) &&
-                 " None of its predecessor is itself?");
-          if (bb1 == bb)
-            pred_bb = bb2;
-          else
-            pred_bb = bb1;
-          return pred_bb;
-        }
-      }
-  assert(0 && " no predecessor?");
-  return NULL;
-}
-
-
-// Construct the prologue
-//
-void 
-ModuloScheduling::constructPrologue(BasicBlock *prologue){
-
-  InstListType & prologue_ist = prologue->getInstList();
-  vvNodeType & tempSchedule_prologue =
-      *(new std::vector<std::vector<ModuloSchedGraphNode*> >(schedule));
-
-  //compute the schedule for prologue
-  unsigned round = 0;
-  unsigned scheduleSize = schedule.size();
-  while (round < scheduleSize / II) {
-    round++;
-    for (unsigned i = 0; i < scheduleSize; ++i) {
-      if (round * II + i >= scheduleSize)
-        break;
-      for (unsigned j = 0; j < schedule[i].size(); ++j) {
-        if (schedule[i][j]) {
-          assert(tempSchedule_prologue[round * II + i][j] == NULL &&
-                 "table not consitent with core table");
-          // move the schedule one iteration ahead and overlap with the original
-          tempSchedule_prologue[round * II + i][j] = schedule[i][j];
-        }
-      }
-    }
-  }
-
-  // Clear the clone memory in the core schedule instructions
-  clearCloneMemory();
-
-  // Fill in the prologue
-  for (unsigned i = 0; i < ceil(1.0 * scheduleSize / II - 1) * II; ++i)
-    for (unsigned j = 0; j < tempSchedule_prologue[i].size(); ++j)
-      if (tempSchedule_prologue[i][j]) {
-
-        //get the instruction
-        Instruction *orn =
-            (Instruction *) tempSchedule_prologue[i][j]->getInst();
-
-        //made a clone of it
-        Instruction *cln = cloneInstSetMemory(orn);
-
-        //insert the instruction
-        prologue_ist.insert(prologue_ist.back(), cln);
-
-        //if there is PHINode in the prologue, the incoming value from itself
-        //should be removed because it is not a loop any longer
-        if (PHINode::classof(cln)) {
-          PHINode *phi = (PHINode *) cln;
-          phi->removeIncomingValue(phi->getParent());
-        }
-      }
-}
-
-
-// Construct the kernel BasicBlock
-//
-void 
-ModuloScheduling::constructKernel(BasicBlock *prologue,
-                                       BasicBlock *kernel,
-                                       BasicBlock *epilogue){
-
-  //*************fill instructions in the kernel****************
-  InstListType & kernel_ist = kernel->getInstList();
-  BranchInst *brchInst;
-  PHINode *phiInst, *phiCln;
-
-  for (unsigned i = 0; i < coreSchedule.size(); ++i)
-    for (unsigned j = 0; j < coreSchedule[i].size(); ++j)
-      if (coreSchedule[i][j]) {
-
-        // Take care of branch instruction differently with normal instructions
-        if (BranchInst::classof(coreSchedule[i][j]->getInst())) {
-          brchInst = (BranchInst *) coreSchedule[i][j]->getInst();
-          continue;
-        }
-        // Take care of PHINode instruction differently with normal instructions
-        if (PHINode::classof(coreSchedule[i][j]->getInst())) {
-          phiInst = (PHINode *) coreSchedule[i][j]->getInst();
-          Instruction *cln = cloneInstSetMemory(phiInst);
-          kernel_ist.insert(kernel_ist.back(), cln);
-          phiCln = (PHINode *) cln;
-          continue;
-        }
-        //for normal instructions: made a clone and insert it in the kernel_ist
-        Instruction *cln =
-            cloneInstSetMemory((Instruction *) coreSchedule[i][j]->
-                               getInst());
-        kernel_ist.insert(kernel_ist.back(), cln);
-      }
-  // The two incoming BasicBlock for PHINode is the prologue and the kernel
-  // (itself)
-  phiCln->setIncomingBlock(0, prologue);
-  phiCln->setIncomingBlock(1, kernel);
-
-  // The incoming value for the kernel (itself) is the new value which is
-  // computed in the kernel
-  Instruction *originalVal = (Instruction *) phiInst->getIncomingValue(1);
-  phiCln->setIncomingValue(1, originalVal->getClone());
-
-  // Make a clone of the branch instruction and insert it in the end
-  BranchInst *cln = (BranchInst *) cloneInstSetMemory(brchInst);
-  kernel_ist.insert(kernel_ist.back(), cln);
-
-  // delete the unconditional branch instruction, which is generated when
-  // splitting the basicBlock
-  kernel_ist.erase(--kernel_ist.end());
-
-  // set the first successor to itself
-  cln->setSuccessor(0, kernel);
-  // set the second successor to eiplogue
-  cln->setSuccessor(1, epilogue);
-
-  //*****change the condition*******
-
-  //get the condition instruction
-  Instruction *cond = (Instruction *) cln->getCondition();
-
-  //get the condition's second operand, it should be a constant
-  Value *operand = cond->getOperand(1);
-  assert(ConstantSInt::classof(operand));
-
-  //change the constant in the condtion instruction
-  ConstantSInt *iteTimes =
-      ConstantSInt::get(operand->getType(),
-                        ((ConstantSInt *) operand)->getValue() - II + 1);
-  cond->setOperand(1, iteTimes);
-
-}
-
-
-// Construct the epilogue 
-//
-void 
-ModuloScheduling::constructEpilogue(BasicBlock *epilogue,
-                                         BasicBlock *succ_bb){
-
-  //compute the schedule for epilogue
-  vvNodeType &tempSchedule_epilogue =
-      *(new std::vector<std::vector<ModuloSchedGraphNode*> >(schedule));
-  unsigned scheduleSize = schedule.size();
-  int round = 0;
-  while (round < ceil(1.0 * scheduleSize / II) - 1) {
-    round++;
-    for (unsigned i = 0; i < scheduleSize; i++) {
-      if (i + round * II >= scheduleSize)
-        break;
-      for (unsigned j = 0; j < schedule[i].size(); j++)
-        if (schedule[i + round * II][j]) {
-          assert(tempSchedule_epilogue[i][j] == NULL
-                 && "table not consitant with core table");
-
-          //move the schdule one iteration behind and overlap
-          tempSchedule_epilogue[i][j] = schedule[i + round * II][j];
-        }
-    }
-  }
-
-  //fill in the epilogue
-  InstListType & epilogue_ist = epilogue->getInstList();
-  for (unsigned i = II; i < scheduleSize; i++)
-    for (unsigned j = 0; j < tempSchedule_epilogue[i].size(); j++)
-      if (tempSchedule_epilogue[i][j]) {
-        Instruction *inst =
-            (Instruction *) tempSchedule_epilogue[i][j]->getInst();
-
-        //BranchInst and PHINode should be treated differently
-        //BranchInst:unecessary, simly omitted
-        //PHINode: omitted
-        if (!BranchInst::classof(inst) && !PHINode::classof(inst)) {
-          //make a clone instruction and insert it into the epilogue
-          Instruction *cln = cloneInstSetMemory(inst);
-          epilogue_ist.push_front(cln);
-        }
-      }
-
-  //*************delete the original instructions****************//
-  //to delete the original instructions, we have to make sure their use is zero
-
-  //update original core instruction's uses, using its clone instread
-  for (unsigned i = 0; i < II; i++)
-    for (unsigned j = 0; j < coreSchedule[i].size(); j++) {
-      if (coreSchedule[i][j])
-        updateUseWithClone((Instruction *) coreSchedule[i][j]->getInst());
-    }
-
-  //erase these instructions
-  for (unsigned i = 0; i < II; i++)
-    for (unsigned j = 0; j < coreSchedule[i].size(); j++)
-      if (coreSchedule[i][j]) {
-        Instruction *ist = (Instruction *) coreSchedule[i][j]->getInst();
-        ist->getParent()->getInstList().erase(ist);
-      }
-
-
-
-  //finally, insert an unconditional branch instruction at the end
-  epilogue_ist.push_back(new BranchInst(succ_bb));
-
-}
-
-
-//------------------------------------------------------------------------------
-//this function replace the value(instruction) ist in other instructions with
-//its latest clone i.e. after this function is called, the ist is not used
-//anywhere and it can be erased.
-//------------------------------------------------------------------------------
-void 
-ModuloScheduling::updateUseWithClone(Instruction * ist){
-
-
-  while (ist->use_size() > 0) {
-    bool destroyed = false;
-
-    //other instruction is using this value ist
-    assert(Instruction::classof(*ist->use_begin()));
-    Instruction *inst = (Instruction *) (*ist->use_begin());
-
-    for (unsigned i = 0; i < inst->getNumOperands(); i++)
-      if (inst->getOperand(i) == ist && ist->getClone()) {
-        // if the instruction is TmpInstruction, simly delete it because it has
-        // no parent and it does not belongs to any BasicBlock
-        if (TmpInstruction::classof(inst)) {
-          delete inst;
-          destroyed = true;
-          break;
-        }
-
-        //otherwise, set the instruction's operand to the value's clone
-        inst->setOperand(i, ist->getClone());
-
-        //the use from the original value ist is destroyed
-        destroyed = true;
-        break;
-      }
-    if (!destroyed) {
-      //if the use can not be destroyed , something is wrong
-      inst->dump();
-      assert(0 && "this use can not be destroyed");
-    }
-  }
-
-}
-
-
-//********************************************************
-//this function clear all clone mememoy
-//i.e. set all instruction's clone memory to NULL
-//*****************************************************
-void 
-ModuloScheduling::clearCloneMemory(){
-
-  for (unsigned i = 0; i < coreSchedule.size(); i++)
-    for (unsigned j = 0; j < coreSchedule[i].size(); j++)
-      if (coreSchedule[i][j])
-        ((Instruction *) coreSchedule[i][j]->getInst())->clearClone();
-
-}
-
-
-//******************************************************************************
-// this function make a clone of the instruction orn the cloned instruction will
-// use the orn's operands' latest clone as its operands it is done this way
-// because LLVM is in SSA form and we should use the correct value
-//this fuction also update the instruction orn's latest clone memory
-//******************************************************************************
-Instruction *
-ModuloScheduling::cloneInstSetMemory(Instruction * orn){
-
-  // make a clone instruction
-  Instruction *cln = orn->clone();
-
-  // update the operands
-  for (unsigned k = 0; k < orn->getNumOperands(); k++) {
-    const Value *op = orn->getOperand(k);
-    if (Instruction::classof(op) && ((Instruction *) op)->getClone()) {
-      Instruction *op_inst = (Instruction *) op;
-      cln->setOperand(k, op_inst->getClone());
-    }
-  }
-
-  // update clone memory
-  orn->setClone(cln);
-  return cln;
-}
-
-
-
-bool 
-ModuloScheduling::ScheduleNode(ModuloSchedGraphNode * node,
-                                    unsigned start, unsigned end,
-                                    NodeVec & nodeScheduled){
-
-  const TargetSchedInfo & msi = target.getSchedInfo();
-  unsigned int numIssueSlots = msi.maxNumIssueTotal;
-
-  if (ModuloScheduling::printScheduleProcess())
-    DEBUG_PRINT(std::cerr << "startTime= " << start << " endTime= " << end << "\n");
-  bool isScheduled = false;
-  for (unsigned i = start; i <= end; i++) {
-    if (ModuloScheduling::printScheduleProcess())
-      DEBUG_PRINT(std::cerr << " now try cycle " << i << ":" << "\n");
-    for (unsigned j = 0; j < numIssueSlots; j++) {
-      unsigned int core_i = i % II;
-      unsigned int core_j = j;
-      if (ModuloScheduling::printScheduleProcess())
-        DEBUG_PRINT(std::cerr << "\t Trying slot " << j << "...........");
-      //check the resouce table, make sure there is no resource conflicts
-      const Instruction *instr = node->getInst();
-      MachineCodeForInstruction & tempMvec =
-          MachineCodeForInstruction::get(instr);
-      bool resourceConflict = false;
-      const TargetInstrInfo & mii = msi.getInstrInfo();
-
-      if (coreSchedule.size() < core_i + 1
-          || !coreSchedule[core_i][core_j]) {
-        //this->dumpResourceUsageTable();
-        int latency = 0;
-        for (unsigned k = 0; k < tempMvec.size(); k++) {
-          MachineInstr *minstr = tempMvec[k];
-          InstrRUsage rUsage = msi.getInstrRUsage(minstr->getOpCode());
-          std::vector < std::vector < resourceId_t > >resources
-              = rUsage.resourcesByCycle;
-          updateResourceTable(resources, i + latency);
-          latency += std::max(mii.minLatency(minstr->getOpCode()), 1);
-        }
-
-        //this->dumpResourceUsageTable();
-
-        latency = 0;
-        if (resourceTableNegative()) {
-
-          //undo-update the resource table
-          for (unsigned k = 0; k < tempMvec.size(); k++) {
-            MachineInstr *minstr = tempMvec[k];
-            InstrRUsage rUsage = msi.getInstrRUsage(minstr->getOpCode());
-            std::vector < std::vector < resourceId_t > >resources
-                = rUsage.resourcesByCycle;
-            undoUpdateResourceTable(resources, i + latency);
-            latency += std::max(mii.minLatency(minstr->getOpCode()), 1);
-          }
-          resourceConflict = true;
-        }
-      }
-      if (!resourceConflict && !coreSchedule[core_i][core_j]) {
-        if (ModuloScheduling::printScheduleProcess()) {
-          DEBUG_PRINT(std::cerr << " OK!" << "\n");
-          DEBUG_PRINT(std::cerr << "Node " << node->getNodeId() << " scheduled.\n");
-        }
-        //schedule[i][j]=node;
-        while (schedule.size() <= i) {
-          std::vector < ModuloSchedGraphNode * >*newCycle =
-              new std::vector < ModuloSchedGraphNode * >();
-          for (unsigned k = 0; k < numIssueSlots; k++)
-            newCycle->push_back(NULL);
-          schedule.push_back(*newCycle);
-        }
-        std::vector<ModuloSchedGraphNode*>::iterator startIterator;
-        startIterator = schedule[i].begin();
-        schedule[i].insert(startIterator + j, node);
-        startIterator = schedule[i].begin();
-        schedule[i].erase(startIterator + j + 1);
-
-        //update coreSchedule
-        //coreSchedule[core_i][core_j]=node;
-        while (coreSchedule.size() <= core_i) {
-          std::vector<ModuloSchedGraphNode*> *newCycle =
-              new std::vector<ModuloSchedGraphNode*>();
-          for (unsigned k = 0; k < numIssueSlots; k++)
-            newCycle->push_back(NULL);
-          coreSchedule.push_back(*newCycle);
-        }
-
-        startIterator = coreSchedule[core_i].begin();
-        coreSchedule[core_i].insert(startIterator + core_j, node);
-        startIterator = coreSchedule[core_i].begin();
-        coreSchedule[core_i].erase(startIterator + core_j + 1);
-
-        node->setSchTime(i);
-        isScheduled = true;
-        nodeScheduled.push_back(node);
-
-        break;
-      } else if (coreSchedule[core_i][core_j]) {
-        if (ModuloScheduling::printScheduleProcess())
-          DEBUG_PRINT(std::cerr << " Slot not available\n");
-      } else {
-        if (ModuloScheduling::printScheduleProcess())
-          DEBUG_PRINT(std::cerr << " Resource conflicts\n");
-      }
-    }
-    if (isScheduled)
-      break;
-  }
-  //assert(nodeScheduled &&"this node can not be scheduled?");
-  return isScheduled;
-}
-
-
-void 
-ModuloScheduling::updateResourceTable(Resources useResources,
-                                           int startCycle){
-
-  for (unsigned i = 0; i < useResources.size(); i++) {
-    int absCycle = startCycle + i;
-    int coreCycle = absCycle % II;
-    std::vector<std::pair<int,int> > &resourceRemained =
-        resourceTable[coreCycle];
-    std::vector < unsigned int >&resourceUsed = useResources[i];
-    for (unsigned j = 0; j < resourceUsed.size(); j++) {
-      for (unsigned k = 0; k < resourceRemained.size(); k++)
-        if ((int) resourceUsed[j] == resourceRemained[k].first) {
-          resourceRemained[k].second--;
-        }
-    }
-  }
-}
-
-void 
-ModuloScheduling::undoUpdateResourceTable(Resources useResources,
-                                               int startCycle){
-
-  for (unsigned i = 0; i < useResources.size(); i++) {
-    int absCycle = startCycle + i;
-    int coreCycle = absCycle % II;
-    std::vector<std::pair<int,int> > &resourceRemained =
-        resourceTable[coreCycle];
-    std::vector < unsigned int >&resourceUsed = useResources[i];
-    for (unsigned j = 0; j < resourceUsed.size(); j++) {
-      for (unsigned k = 0; k < resourceRemained.size(); k++)
-        if ((int) resourceUsed[j] == resourceRemained[k].first) {
-          resourceRemained[k].second++;
-        }
-    }
-  }
-}
-
-
-//-----------------------------------------------------------------------
-// Function: resourceTableNegative
-// return value:
-//   return false if any element in the resouceTable is negative
-//   otherwise return true
-// Purpose:
-
-//   this function is used to determine if an instruction is eligible for
-//   schedule at certain cycle
-//-----------------------------------------------------------------------
-
-
-bool 
-ModuloScheduling::resourceTableNegative(){
-
-  assert(resourceTable.size() == (unsigned) II
-         && "resouceTable size must be equal to II");
-  bool isNegative = false;
-  for (unsigned i = 0; i < resourceTable.size(); i++)
-    for (unsigned j = 0; j < resourceTable[i].size(); j++) {
-      if (resourceTable[i][j].second < 0) {
-        isNegative = true;
-        break;
-      }
-    }
-  return isNegative;
-}
-
-
-//----------------------------------------------------------------------
-// Function: dumpResouceUsageTable
-// Purpose:
-//   print out ResouceTable for debug
-//
-//------------------------------------------------------------------------
-
-void 
-ModuloScheduling::dumpResourceUsageTable(){
-
-  DEBUG_PRINT(std::cerr << "dumping resource usage table\n");
-  for (unsigned i = 0; i < resourceTable.size(); i++) {
-    for (unsigned j = 0; j < resourceTable[i].size(); j++)
-      DEBUG_PRINT(std::cerr << resourceTable[i][j].first 
-            << ":" << resourceTable[i][j].second << " ");
-    DEBUG_PRINT(std::cerr << "\n");
-  }
-
-}
-
-//----------------------------------------------------------------------
-//Function: dumpSchedule
-//Purpose:
-//       print out thisSchedule for debug
-//
-//-----------------------------------------------------------------------
-void 
-ModuloScheduling::dumpSchedule(vvNodeType thisSchedule){
-
-  const TargetSchedInfo & msi = target.getSchedInfo();
-  unsigned numIssueSlots = msi.maxNumIssueTotal;
-  for (unsigned i = 0; i < numIssueSlots; i++)
-    DEBUG_PRINT(std::cerr << "\t#");
-  DEBUG_PRINT(std::cerr << "\n");
-  for (unsigned i = 0; i < thisSchedule.size(); i++) {
-    DEBUG_PRINT(std::cerr << "cycle" << i << ": ");
-    for (unsigned j = 0; j < thisSchedule[i].size(); j++)
-      if (thisSchedule[i][j] != NULL)
-        DEBUG_PRINT(std::cerr << thisSchedule[i][j]->getNodeId() << "\t");
-      else
-        DEBUG_PRINT(std::cerr << "\t");
-    DEBUG_PRINT(std::cerr << "\n");
-  }
-}
-
-
-//----------------------------------------------------
-//Function: dumpScheduling
-//Purpose:
-//   print out the schedule and coreSchedule for debug      
-//
-//-------------------------------------------------------
-
-void 
-ModuloScheduling::dumpScheduling(){
-
-  DEBUG_PRINT(std::cerr << "dump schedule:" << "\n");
-  const TargetSchedInfo & msi = target.getSchedInfo();
-  unsigned numIssueSlots = msi.maxNumIssueTotal;
-  for (unsigned i = 0; i < numIssueSlots; i++)
-    DEBUG_PRINT(std::cerr << "\t#");
-  DEBUG_PRINT(std::cerr << "\n");
-  for (unsigned i = 0; i < schedule.size(); i++) {
-    DEBUG_PRINT(std::cerr << "cycle" << i << ": ");
-    for (unsigned j = 0; j < schedule[i].size(); j++)
-      if (schedule[i][j] != NULL)
-        DEBUG_PRINT(std::cerr << schedule[i][j]->getNodeId() << "\t");
-      else
-        DEBUG_PRINT(std::cerr << "\t");
-    DEBUG_PRINT(std::cerr << "\n");
-  }
-
-  DEBUG_PRINT(std::cerr << "dump coreSchedule:" << "\n");
-  for (unsigned i = 0; i < numIssueSlots; i++)
-    DEBUG_PRINT(std::cerr << "\t#");
-  DEBUG_PRINT(std::cerr << "\n");
-  for (unsigned i = 0; i < coreSchedule.size(); i++) {
-    DEBUG_PRINT(std::cerr << "cycle" << i << ": ");
-    for (unsigned j = 0; j < coreSchedule[i].size(); j++)
-      if (coreSchedule[i][j] != NULL)
-        DEBUG_PRINT(std::cerr << coreSchedule[i][j]->getNodeId() << "\t");
-      else
-        DEBUG_PRINT(std::cerr << "\t");
-    DEBUG_PRINT(std::cerr << "\n");
-  }
-}
-
-/*
-  print out final schedule
-*/
-
-void 
-ModuloScheduling::dumpFinalSchedule(){
-
-  std::cerr << "dump schedule:" << "\n";
-  const TargetSchedInfo & msi = target.getSchedInfo();
-  unsigned numIssueSlots = msi.maxNumIssueTotal;
-
-  for (unsigned i = 0; i < numIssueSlots; i++)
-    std::cerr << "\t#";
-  std::cerr << "\n";
-
-  for (unsigned i = 0; i < schedule.size(); i++) {
-    std::cerr << "cycle" << i << ": ";
+  class ModuloScheduling : public FunctionPass {
     
-    for (unsigned j = 0; j < schedule[i].size(); j++)
-      if (schedule[i][j] != NULL)
-        std::cerr << schedule[i][j]->getNodeId() << "\t";
-      else
-        std::cerr << "\t";
-    std::cerr << "\n";
-  }
-  
-  std::cerr << "dump coreSchedule:" << "\n";
-  for (unsigned i = 0; i < numIssueSlots; i++)
-    std::cerr << "\t#";
-  std::cerr << "\n";
-  
-  for (unsigned i = 0; i < coreSchedule.size(); i++) {
-    std::cerr << "cycle" << i << ": ";
-    for (unsigned j = 0; j < coreSchedule[i].size(); j++)
-      if (coreSchedule[i][j] != NULL)
-        std::cerr << coreSchedule[i][j]->getNodeId() << "\t";
-      else
-        std::cerr << "\t";
-    std::cerr << "\n";
-  }
-}
-
-//---------------------------------------------------------------------------
-// Function: ModuloSchedulingPass
-// 
-// Purpose:
-//   Entry point for Modulo Scheduling
-//   Schedules LLVM instruction
-//   
-//---------------------------------------------------------------------------
-
-namespace {
-  class ModuloSchedulingPass:public FunctionPass {
-    const TargetMachine &target;
-
   public:
-    ModuloSchedulingPass(const TargetMachine &T):target(T) {}
-
-    const char *getPassName() const {
-      return "Modulo Scheduling";
-    }
-
-    // getAnalysisUsage - We use LiveVarInfo...
-    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-      //AU.addRequired(FunctionLiveVarInfo::ID);
-    }
-    
-    bool runOnFunction(Function & F);
+    virtual bool runOnFunction(Function &F);
   };
-}                               // end anonymous namespace
 
+  RegisterOpt<ModuloScheduling> X("modulo-sched", "Modulo Scheduling/Software Pipelining");
+}
 
-bool
-ModuloSchedulingPass::runOnFunction(Function &F){
-  
-  ModuloSchedGraphSet *graphSet = new ModuloSchedGraphSet(&F, target);
-
-  ModuloSchedulingSet ModuloSchedulingSet(*graphSet);
-  
-  DEBUG_PRINT(std::cerr<<"runOnFunction  in ModuloSchedulingPass returns\n"<<"\n");
-  return false;
+//Create Modulo Scheduling Pass
+Pass *createModuloSchedPass() {
+  return new ModuloScheduling(); 
 }
 
+//ModuloScheduling::runOnFunction - Main transformation entry point.
+bool ModuloScheduling::runOnFunction(Function &F) {
+  bool Changed = false;
 
-Pass *
-createModuloSchedulingPass(const TargetMachine & tgt){
-  DEBUG_PRINT(std::cerr<<"creating modulo scheduling\n");
-  return new ModuloSchedulingPass(tgt);
+  return Changed;
 }
+
diff --git a/lib/CodeGen/ModuloScheduling/ModuloScheduling.h b/lib/CodeGen/ModuloScheduling/ModuloScheduling.h
deleted file mode 100644
index 00cca149da..0000000000
--- a/lib/CodeGen/ModuloScheduling/ModuloScheduling.h
+++ /dev/null
@@ -1,194 +0,0 @@
-// ModuloScheduling.h -------------------------------------------*- C++ -*-===//
-//
-// This header defines the the classes ModuloScheduling and 
-// ModuloSchedulingSet's structure
-//
-//===----------------------------------------------------------------------===//
-
-
-#ifndef LLVM_CODEGEN_MODULOSCHEDULING_H
-#define LLVM_CODEGEN_MODULOSCHEDULING_H
-
-#include "ModuloSchedGraph.h"
-#include <iostream>
-#include <vector>
-
-//#define DEBUG_PRINT(x) x
-
-#define DEBUG_PRINT(x) 
-
-// for debug information selecton
-enum ModuloSchedDebugLevel_t { 
-  ModuloSchedDebugLevel_NoDebugInfo,
-  ModuloSchedDebugLevel_PrintSchedule,
-  ModuloSchedDebugLevel_PrintScheduleProcess,
-};
-
-class ModuloScheduling: NonCopyable {
-private:
-
-  typedef std::vector<ModuloSchedGraphNode*> NodeVec;
-  typedef std::vector<std::vector<unsigned> > Resources;
-
-  // The graph to feed in
-  ModuloSchedGraph &graph;
-  const TargetMachine &target;
-
-  // The BasicBlock to be scheduled
-  BasicBlock *bb;
-
-  // Iteration Interval
-  // FIXME: II may be a better name for its meaning
-  unsigned II;
-
-  // The vector containing the nodes which have been scheduled
-  NodeVec nodeScheduled;
-
-  // The remaining unscheduled nodes 
-  const NodeVec &oNodes;
-
-  // The machine resource table
-  std::vector<std::vector<std::pair<int,int> > > resourceTable;
-
-  ///the schedule( with many schedule stage)
-  std::vector<std::vector<ModuloSchedGraphNode*> > schedule;
-
-  ///the kernel(core) schedule(length = II)
-  std::vector<std::vector<ModuloSchedGraphNode*> > coreSchedule;
-
-  typedef BasicBlock::InstListType InstListType;
-  typedef std::vector<std::vector<ModuloSchedGraphNode*> > vvNodeType;
-
-
-
-
-
-public:
-
-  ModuloScheduling(ModuloSchedGraph & _graph):
-    graph(_graph), target(graph.getTarget()), oNodes(graph.getONodes())
-  {
-    II = graph.getMII();
-    bb = graph.getBasicBlock();
-    instrScheduling();
-  };
-
-  ~ModuloScheduling() {};
-
-
-
-  static bool 
-  printSchedule() { 
-
-    //return ModuloScheduling::DebugLevel >= DebugLevel_PrintSchedule; 
-    return true;
-
-    
-  }
-  static bool 
-  printScheduleProcess() {
-  
-    //return DebugLevel >= DebugLevel_PrintScheduleProcess;
-    return true;
-
-
-  }
-
-  // The method to compute schedule and instert epilogue and prologue
-  void instrScheduling();
-
-  // Debug functions:
-  // Dump the schedule and core schedule
-  void dumpScheduling();
-  void dumpFinalSchedule();
-
-  // Dump the input vector of nodes
-  // sch: the input vector of nodes
-  void dumpSchedule(std::vector<std::vector<ModuloSchedGraphNode*> > sch);
-
-  // Dump the resource usage table
-  void dumpResourceUsageTable();
-
-  //*******************internal functions*******************************
-private:
-  //clear memory from the last round and initialize if necessary
-  void clearInitMem(const TargetSchedInfo&);
-
-  //compute schedule and coreSchedule with the current II
-  bool computeSchedule();
-
-  BasicBlock *getSuccBB(BasicBlock *);
-  BasicBlock *getPredBB(BasicBlock *);
-  void constructPrologue(BasicBlock *prologue);
-  void constructKernel(BasicBlock *prologue,
-                       BasicBlock *kernel,
-                       BasicBlock *epilogue);
-  void constructEpilogue(BasicBlock *epilogue, BasicBlock *succ_bb);
-
-  // update the resource table at the startCycle
-  // vec: the resouce usage
-  // startCycle: the start cycle the resouce usage is
-  void updateResourceTable(std::vector<std::vector<unsigned> > vec,
-                           int startCycle);
-
-  // un-do the update in the resource table in the startCycle
-  // vec: the resouce usage
-  // startCycle: the start cycle the resouce usage is
-  void undoUpdateResourceTable(std::vector<std::vector<unsigned> > vec,
-                               int startCycle);
-
-  // return whether the resourcetable has negative element
-  // this function is called after updateResouceTable() to determine whether a
-  // node can be scheduled at certain cycle
-  bool resourceTableNegative();
-
-  // try to Schedule the node starting from start to end cycle(inclusive)
-  // if it can be scheduled, put it in the schedule and update nodeScheduled
-  // node: the node to be scheduled
-  // start: start cycle
-  // end : end cycle
-  // nodeScheduled: a vector storing nodes which has been scheduled
-  bool ScheduleNode(ModuloSchedGraphNode * node, unsigned start,
-                    unsigned end, NodeVec &nodeScheduled);
-
-  //each instruction has a memory of the latest clone instruction
-  //the clone instruction can be get using getClone() 
-  //this function clears the memory, i.e. getClone() after calling this function
-  //returns null
-  void clearCloneMemory();
-
-  //this fuction make a clone of this input Instruction and update the clone
-  //memory
-  //inst: the instrution to be cloned
-  Instruction *cloneInstSetMemory(Instruction *inst);
-
-  //this function update each instrutions which uses ist as its operand
-  //after update, each instruction will use ist's clone as its operand
-  void updateUseWithClone(Instruction * ist);
-
-};
-
-
-class ModuloSchedulingSet:
-NonCopyable {
-private:
-
-  //the graphSet to feed in
-  ModuloSchedGraphSet & graphSet;
-
-public:
-
-  //constructor
-  //Scheduling graph one by one
-  ModuloSchedulingSet(ModuloSchedGraphSet _graphSet): graphSet(_graphSet) {
-    for (unsigned i = 0; i < graphSet.size(); i++) {
-      ModuloSchedGraph & graph = *(graphSet[i]);
-      if (graph.isLoop(graph.getBasicBlock()))
-        ModuloScheduling ModuloScheduling(graph);
-    }
-  };
-
-  ~ModuloSchedulingSet() {};
-};
-
-#endif
diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedGraph.cpp b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedGraph.cpp
index a29722aa61..1bdbb1a976 100644
--- a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedGraph.cpp
+++ b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedGraph.cpp
@@ -1,1507 +1,130 @@
-//===- ModuloSchedGraph.cpp - Graph datastructure for Modulo Scheduling ---===//
-//
-//
+//===- ModuloSchedGraph.cpp - Modulo Scheduling Graph and Set -*- C++ -*---===//
+// 
+// Description here
 //===----------------------------------------------------------------------===//
 
-#include "llvm/CodeGen/InstrSelection.h"
-#include "llvm/Function.h"
-#include "llvm/Instructions.h"
-#include "llvm/Type.h"
-#include "llvm/CodeGen/MachineCodeForInstruction.h"
-#include "llvm/CodeGen/MachineInstr.h"
-#include "llvm/Target/TargetSchedInfo.h"
-#include "Support/StringExtras.h"
-#include "Support/STLExtras.h"
-#include "Support/hash_map"
-#include "Support/Statistic.h"
-#include "ModuloScheduling.h"
 #include "ModuloSchedGraph.h"
-#include <algorithm>
-#include <ostream>
-#include <vector>
-#include <math.h>
-
-
-#define UNIDELAY 1
-
-using std::cerr;
-using std::endl;
-using std::vector;
-
-
-/***********member functions for ModuloSchedGraphNode*********/
-
-
-ModuloSchedGraphNode::ModuloSchedGraphNode(unsigned int in_nodeId,
-                                           const BasicBlock * in_bb,
-                                           const Instruction * in_inst,
-                                           int indexInBB,
-                                           const TargetMachine & target)
-  :SchedGraphNodeCommon(in_nodeId, indexInBB), inst(in_inst){
-  
-  if (inst) {
-    //FIXME: find the latency 
-    //currently set the latency to zero
-    latency = 0;
-  }
-}
-
-
-/***********member functions for ModuloSchedGraph*********/
-
-void 
-ModuloSchedGraph::addDefUseEdges(const BasicBlock *bb){
-  
-  //collect def instructions, store them in vector
-  const TargetInstrInfo & mii = target.getInstrInfo();
-  vector < ModuloSchedGraphNode * > 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 ins = bb->begin(), E = bb->end();
-           ins != E; ++ins)
-        if ((const Instruction *) ins == inst) {
-          node = (*this)[inst];
-          break;
-        }
-
-
-      if (node == NULL){
-	
-	//inst is not an instruction in this block
-	//do nothing
-
-      } else {
-        // Add a flow edge from the def instruction to the ref instruction
-	// This is a true dependence, so the delay is equal to the 
-	//delay of the preceding node.
-	
-        int delay = 0;
-	
-        // self loop will not happen in SSA form
-        assert(defVec[i] != node && "same node?");
-
-        MachineCodeForInstruction & tempMvec =
-            MachineCodeForInstruction::get(value);
-        for (unsigned j = 0; j < tempMvec.size(); j++) {
-          MachineInstr *temp = tempMvec[j];
-          delay = std::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,*toInst;
-    int toType, fromType;
-    
-    //get the first mem instruction and instruction type
-    fromInst = memNodeVec[im]->getInst();
-    fromType = CallInst::classof(fromInst) ? SG_CALL_REF
-      : LoadInst::classof(fromInst) ? SG_LOAD_REF : SG_STORE_REF;
-    
-    for (unsigned jm = im + 1; jm < NM; jm++) {
-      
-      //get the second mem instruction and instruction type
-      toInst = memNodeVec[jm]->getInst();
-      toType = CallInst::classof(toInst) ? SG_CALL_REF
-          : LoadInst::classof(toInst) ? SG_LOAD_REF : SG_STORE_REF;
-      
-      //add two edges if not both of them are LOAD instructions
-      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);
-
-	//set the iteration difference for this edge to 1.
-        edge->setIteDiff(1);
-	
-      }
-    }
-  }
-}
-
-/*
-  this function build graph nodes for each instruction 
-  in the basicblock
-*/
-
-void 
-ModuloSchedGraph::buildNodesforBB(const TargetMachine &target,
-				  const BasicBlock *bb){
-  
-  int i = 0;
-  ModuloSchedGraphNode *node;
-
-  for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); 
-       I != E; ++I) {
-    
-    node=new ModuloSchedGraphNode(getNumNodes(), bb, I, i, target);
-    
-    i++;
-    
-    this->addHash(I, node);
-  }
-
-}
-
-
-/*
-  determine if this basicblock includes a loop or not
-*/
-
-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;
-
-}
-
-/*
-  compute every node's ASAP
-
-*/
-
-//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.
-
-void 
-ModuloSchedGraph::computeNodeASAP(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->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 = std::max(node->ASAP, temp);
-    }
-    node->setPropertyComputed(true);
-  }
-}
-
-
-/*
-  compute every node's ALAP in the basic block
-*/
-
-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);
-    maxASAP = std::max(maxASAP, node->ASAP);
-
-  }
-
-  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 = std::min(node->ALAP, temp);
-      
-    }
-    node->setPropertyComputed(true);
-  }
-}
-
-/*
-  compute every node's mov in this basicblock
-*/
-
-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? ");
-    
-  }
-
-}
-
-
-/*
-  compute every node's depth in this basicblock
-*/
-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 = std::max(node->depth, temp);
-    }
-    node->setPropertyComputed(true);
-
-  }
-  
-}
-
-
-/*
-  compute every node's height in this basic block
-*/
-
-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 = std::max(node->height, succ->height + edge->getMinDelay());
-      
-    }
-    node->setPropertyComputed(true);
-  }
-  
-}
-
-/*
-  compute every node's property in a basicblock
-*/
-
-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);
-}
-
-
-/*
-  compute the preset of this set without considering the edges
-  between backEdgeSrc and backEdgeSink
-*/
-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 edges between backEdgeSrc and backEdgeSink, omitted
-      if (edge->getSrc()->getNodeId() == backEdgeSrc
-          && edge->getSink()->getNodeId() == backEdgeSink)
-        continue;
-      ModuloSchedGraphNode *pred =
-          (ModuloSchedGraphNode *) (edge->getSrc());
-
-      //if pred is not in the predSet ....
-      bool alreadyInset = false;
-      for (unsigned j = 0; j < predS.size(); ++j)
-        if (predS[j]->getNodeId() == pred->getNodeId()) {
-          alreadyInset = true;
-          break;
-        }
-
-      // and pred is not in the set ....
-      for (unsigned j = 0; j < set.size(); ++j)
-        if (set[j]->getNodeId() == pred->getNodeId()) {
-          alreadyInset = true;
-          break;
-        }
-
-      //push it into the predS
-      if (!alreadyInset)
-        predS.push_back(pred);
-    }
-  }
-  return predS;
-}
-
-
-/*
-  return pred set to this set
-*/
-
-ModuloSchedGraph::NodeVec 
-ModuloSchedGraph::predSet(NodeVec set){
-  
-  //node number increases from 2,   
-  return predSet(set, 0, 0);
-}
-
-/*
-  return pred set to  _node, ignoring 
-  any edge between backEdgeSrc and backEdgeSink
-*/
-std::vector <ModuloSchedGraphNode*>
-ModuloSchedGraph::predSet(ModuloSchedGraphNode *_node,
-                          unsigned backEdgeSrc, unsigned backEdgeSink){
-
-  std::vector<ModuloSchedGraphNode*> set;
-  set.push_back(_node);
-  return predSet(set, backEdgeSrc, backEdgeSink);
-}
-
-
-/*
-  return pred set to  _node, ignoring 
-*/
-
-std::vector <ModuloSchedGraphNode*>
-ModuloSchedGraph::predSet(ModuloSchedGraphNode * _node){
-  
-  return predSet(_node, 0, 0);
-  
-}
-
-/*
-  return successor set to the input set
-  ignoring any edge between src and sink
-*/
-
-std::vector<ModuloSchedGraphNode*>
-ModuloSchedGraph::succSet(std::vector<ModuloSchedGraphNode*> set, 
-                          unsigned src, unsigned sink){
-  
-  std::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 the edge is between src and sink, skip
-      if (edge->getSrc()->getNodeId() == src
-          && edge->getSink()->getNodeId() == sink)
-        continue;
-      ModuloSchedGraphNode *succ =
-          (ModuloSchedGraphNode *) (edge->getSink());
-
-      //if pred is not in the successor set ....
-      bool alreadyInset = false;
-      for (unsigned j = 0; j < succS.size(); j++)
-        if (succS[j]->getNodeId() == succ->getNodeId()) {
-          alreadyInset = true;
-          break;
-        }
-
-      //and not in this set ....
-      for (unsigned j = 0; j < set.size(); j++)
-        if (set[j]->getNodeId() == succ->getNodeId()) {
-          alreadyInset = true;
-          break;
-        }
-
-      //push it into the successor set
-      if (!alreadyInset)
-        succS.push_back(succ);
-    }
-  }
-  return succS;
-}
-
-/*
-  return successor set to the input set
-*/
-
-ModuloSchedGraph::NodeVec ModuloSchedGraph::succSet(NodeVec set){
-
-  return succSet(set, 0, 0);
+#include "llvm/Type.h"
 
+ModuloSchedGraphNode::ModuloSchedGraphNode(unsigned id, int index, 
+					   const Instruction *inst, 
+					   const TargetMachine &targ) 
+  : SchedGraphNodeCommon(id, index), Inst(inst), Target(targ) {
 }
 
-/*
-  return successor set to the input node
-  ignoring any edge between src and sink
-*/
-
-std::vector<ModuloSchedGraphNode*>
-ModuloSchedGraph::succSet(ModuloSchedGraphNode *_node,
-                          unsigned src, unsigned sink){
-
-  std::vector<ModuloSchedGraphNode*>set;
-
-  set.push_back(_node);
-  
-  return succSet(set, src, sink);
-  
+void ModuloSchedGraphNode::print(std::ostream &os) const {
+  os << "Modulo Scheduling Node\n";
 }
 
-/*
-  return successor set to the input node
-*/
-
-std::vector<ModuloSchedGraphNode*>
-ModuloSchedGraph::succSet(ModuloSchedGraphNode * _node){
-  
-  return succSet(_node, 0, 0);
-  
-}
+ModuloSchedGraph::ModuloSchedGraph(const BasicBlock *bb, const TargetMachine &targ) 
+  : SchedGraphCommon(), BB(bb), Target(targ) {
 
+  assert(BB != NULL && "Basic Block is null");
 
-/*
-  find maximum delay between srcId and sinkId
-*/
+  //Builds nodes from each instruction in the basic block
+  buildNodesForBB();
 
-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;
-  
 }
 
-/*
-  dump all circuits found
-*/
-
-void 
-ModuloSchedGraph::dumpCircuits(){
-  
-  DEBUG_PRINT(std::cerr << "dumping circuits for graph:\n");
-  int j = -1;
-  while (circuits[++j][0] != 0) {
-    int k = -1;
-    while (circuits[j][++k] != 0)
-      DEBUG_PRINT(std::cerr << circuits[j][k] << "\t");
-    DEBUG_PRINT(std::cerr << "\n");
+void ModuloSchedGraph::buildNodesForBB() {
+  int count = 0;
+  for (BasicBlock::const_iterator i = BB->begin(), e = BB->end(); i != e; ++i) {
+    addNode(i,new ModuloSchedGraphNode(size(), count, i, Target));
+    count++;
   }
-}
 
-/*
-  dump all sets found
-*/
+	    //Get machine instruction(s) for the llvm instruction
+	    //MachineCodeForInstruction &MC = MachineCodeForInstruction::get(Node->first);
+	    
 
-void 
-ModuloSchedGraph::dumpSet(std::vector < ModuloSchedGraphNode * >set){
-  
-  for (unsigned i = 0; i < set.size(); i++)
-    DEBUG_PRINT(std::cerr << set[i]->getNodeId() << "\t");
-  DEBUG_PRINT(std::cerr << "\n");
-  
 }
 
-/*
-  return union of set1 and set2
-*/
-
-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;
+void ModuloSchedGraph::addNode(const Instruction *I,
+			       ModuloSchedGraphNode *node) {
+  assert(node!= NULL && "New ModuloSchedGraphNode is null");
+  GraphMap[I] = node;
 }
 
-/*
-  return conjuction of set1 and set2
-*/
-std::vector<ModuloSchedGraphNode*>
-ModuloSchedGraph::vectorConj(std::vector<ModuloSchedGraphNode*> set1,
-                             std::vector<ModuloSchedGraphNode*> set2){
+void ModuloSchedGraph::addDepEdges() {
   
-  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;
-
-}
-
-/*
-  return the result of subtracting set2 from set1 
-  (set1 -set2)
-*/
-ModuloSchedGraph::NodeVec 
-ModuloSchedGraph::vectorSub(NodeVec set1,
-			    NodeVec set2){
+  //Get Machine target information for calculating delay
+  const TargetInstrInfo &MTI = Target.getInstrInfo();
   
-  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);
+  //Loop over instruction in BB and gather dependencies
+  for(BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
     
-  }
-  
-  return newVec;
-  
-}
-
-/*
-  order all nodes in the basicblock
-  based on the sets information and node property
-
-  output: ordered nodes are stored in oNodes
-*/
-
-void ModuloSchedGraph::orderNodes() {
-  oNodes.clear();
-
-  std::vector < ModuloSchedGraphNode * >set;
-  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 (ModuloScheduling::printScheduleProcess())
-    DEBUG_PRINT(std::cerr << "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 (ModuloScheduling::printScheduleProcess()) {
-    DEBUG_PRINT(std::cerr << "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 (ModuloScheduling::printScheduleProcess())
-          DEBUG_PRINT(std::cerr << "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 (ModuloScheduling::printScheduleProcess())
-          DEBUG_PRINT(std::cerr << "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 (ModuloScheduling::printScheduleProcess()) {
-      DEBUG_PRINT(std::cerr << "order finished\n");
-      DEBUG_PRINT(std::cerr << "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 (ModuloScheduling::printScheduleProcess())
-      DEBUG_PRINT(std::cerr << "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 (ModuloScheduling::printScheduleProcess())
-        DEBUG_PRINT(std::cerr << "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));
+    //Ignore instructions of the void type
+    if(I->getType() != Type::VoidTy) {
+      
+      //Iterate over def-use chain and add true dependencies
+      for (Value::use_const_iterator U = I->use_begin(), e = I->use_end(); U != e; 
+	   ++U) {
+	if (Instruction *Inst = dyn_cast<Instruction>(*U)) {
+	  //Check if a node already exists for this instruction
+	  ModuloSchedGraph::iterator Sink = find(Inst);
+	  
+	  //If the instruction is in our graph, add appropriate edges
+	  if(Sink->second != NULL) {
+	    //assert if self loop
+	    assert(&*I == Sink->first && "Use edge to itself!");
+	    
+	    //Create edge and set delay equal to node latency
+	    //FIXME: Is it safe to do this?
+	    ModuloSchedGraph::iterator Src = find(I);
+	    SchedGraphEdge *trueDep = new SchedGraphEdge(&*Src->second ,&*Sink->second, &*I,
+							 SchedGraphEdge::TrueDep,
+							 Src->second->getLatency());
+	    //Determine the iteration difference
+	    //FIXME: Will this ever happen?
+	  }
+	}
       }
     }
-    if (ModuloScheduling::printScheduleProcess()) {
-      DEBUG_PRINT(std::cerr << "next set is:\n");
-      dumpSet(set);
-    }
-  }  
-
-}
-
-
-
-/*
-
-  build graph for instructions in this basic block
-
-*/
-void ModuloSchedGraph::buildGraph(const TargetMachine & target)
-{
-  
-  assert(this->bb && "The basicBlock is NULL?");
-  
-  // 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);
-
-  if (ModuloScheduling::printScheduleProcess())
-    this->dump(bb);
-  
-  if (isLoop(bb)) {
-    
-    DEBUG_PRINT(cerr << "building nodes for this BasicBlock\n");
-    buildNodesforBB(target, bb);
     
-    DEBUG_PRINT(cerr << "adding def-use edge to this basic block\n");
-    this->addDefUseEdges(bb);
-
-    DEBUG_PRINT(cerr << "adding CD edges to this basic block\n");
-    this->addCDEdges(bb);
-
-    DEBUG_PRINT(cerr << "adding memory edges to this basicblock\n");
-    this->addMemEdges(bb);
-    
-    int ResII = this->computeResII(bb);
-
-    if (ModuloScheduling::printScheduleProcess())
-      DEBUG_PRINT(std::cerr << "ResII is " << ResII << "\n");
-
-    int RecII = this->computeRecII(bb);
-    if (ModuloScheduling::printScheduleProcess())
-      DEBUG_PRINT(std::cerr << "RecII is " << RecII << "\n");
-    
-    this->MII = std::max(ResII, RecII);
-
-    this->computeNodeProperty(bb);
-    if (ModuloScheduling::printScheduleProcess())
-      this->dumpNodeProperty();
-
-    this->orderNodes();
-    
-    if (ModuloScheduling::printScheduleProcess())
-      this->dump();
-
   }
-}
-
-/*
-  get node with nodeId
-*/
-
-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;
-  
-}
-
-/*
-  compute RecurrenceII
-*/
-
-int 
-ModuloSchedGraph::computeRecII(const BasicBlock *bb){
-
-  int RecII = 0;
-
-
-  //FIXME: only deal with circuits starting at the first node: the phi node
-  //nodeId=2;
-
-  //search all elementary circuits in the dependence 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
-  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();
-    // DEBUG_PRINT(std::cerr<<"current node is "<<currentNodeId<<"\n");
-
-    ModuloSchedGraphNode *nextNode = NULL;
-    for (ModuloSchedGraphNode::const_iterator I =
-         currentNode->beginOutEdges(), E = currentNode->endOutEdges();
-         I != E; I++) {
-      //DEBUG_PRINT(std::cerr <<" searching in outgoint edges of node
-      //"<<currentNodeId<<"\n";
-      unsigned nodeId = ((SchedGraphEdge *) * I)->getSink()->getNodeId();
-      bool inpath = false, instack = false;
-      int k;
-
-      //DEBUG_PRINT(std::cerr<<"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) {
-      //DEBUG_PRINT(std::cerr<<"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 {
-      //DEBUG_PRINT(std::cerr<<"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 (ModuloScheduling::printScheduleProcess())
-        DEBUG_PRINT(std::cerr << "circuits found are:\n");
-      int j = -1;
-      while (circuits[++j][0] != 0) {
-        int k = -1;
-        while (circuits[j][++k] != 0)
-          if (ModuloScheduling::printScheduleProcess())
-            DEBUG_PRINT(std::cerr << circuits[j][k] << "\t");
-        if (ModuloScheduling::printScheduleProcess())
-          DEBUG_PRINT(std::cerr << "\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];
-
-          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 (ModuloScheduling::printScheduleProcess())
-          DEBUG_PRINT(std::cerr << "The total Delay in the circuit is " << sumDelay
-                << "\n");
-
-        RecII = RecII > sumDelay ? RecII : sumDelay;
-
-      }
-      return RecII;
-    }
-
-  }
-
-  return -1;
-}
-
-/*
-  update resource usage vector (ruVec)
-*/
-void 
-ModuloSchedGraph::addResourceUsage(std::vector<std::pair<int,int> > &ruVec,
-				   int rid){
   
-  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));
-
 }
 
-/*
-  dump the resource usage vector
-*/
-
-void 
-ModuloSchedGraph::dumpResourceUsage(std::vector<std::pair<int,int> > &ru){
-
-  TargetSchedInfo & msi = (TargetSchedInfo &) target.getSchedInfo();
-  
-  std::vector<std::pair<int,int> > resourceNumVector = msi.resourceNumVector;
-  DEBUG_PRINT(std::cerr << "resourceID\t" << "resourceNum\n");
-  for (unsigned i = 0; i < resourceNumVector.size(); i++)
-    DEBUG_PRINT(std::cerr << resourceNumVector[i].
-        first << "\t" << resourceNumVector[i].second << "\n");
+void ModuloSchedGraph::ASAP() {
 
-  DEBUG_PRINT(std::cerr << " maxNumIssueTotal(issue slot in one cycle) = " << msi.
-        maxNumIssueTotal << "\n");
-  DEBUG_PRINT(std::cerr << "resourceID\t resourceUsage\t ResourceNum\n");
-  for (unsigned i = 0; i < ru.size(); i++) {
-    DEBUG_PRINT(std::cerr << ru[i].first << "\t" << ru[i].second);
-    const unsigned resNum = msi.getCPUResourceNum(ru[i].first);
-    DEBUG_PRINT(std::cerr << "\t" << resNum << "\n");
 
-  }  
 }
 
-/*
-  compute thre resource restriction II
-*/
+void ModuloSchedGraph::ALAP() {
 
-int 
-ModuloSchedGraph::computeResII(const BasicBlock * bb){
-  
-  const TargetInstrInfo & mii = target.getInstrInfo();
-  const TargetSchedInfo & msi = target.getSchedInfo();
-  
-  int ResII;
-  std::vector<std::pair<int,int> > resourceUsage;
-
-  for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); I != E;
-       I++) {
-    if (ModuloScheduling::printScheduleProcess()) {
-      DEBUG_PRINT(std::cerr << "machine instruction for llvm instruction( node " <<
-            getGraphNodeForInst(I)->getNodeId() << ")\n");
-      DEBUG_PRINT(std::cerr << "\t" << *I);
-    }
-    MachineCodeForInstruction & tempMvec =
-        MachineCodeForInstruction::get(I);
-    if (ModuloScheduling::printScheduleProcess())
-      DEBUG_PRINT(std::cerr << "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 (ModuloScheduling::printScheduleProcess())
-        DEBUG_PRINT(std::cerr << "resources Usage for this Instr(totCycles="
-              << totCycles << ",mindLatency="
-              << mii.minLatency(minstr->getOpCode()) << "): " << *minstr
-              << "\n");
-      for (unsigned j = 0; j < resources.size(); j++) {
-        if (ModuloScheduling::printScheduleProcess())
-          DEBUG_PRINT(std::cerr << "cycle " << j << ": ");
-        for (unsigned k = 0; k < resources[j].size(); k++) {
-          if (ModuloScheduling::printScheduleProcess())
-            DEBUG_PRINT(std::cerr << "\t" << resources[j][k]);
-          addResourceUsage(resourceUsage, resources[j][k]);
-        }
-        if (ModuloScheduling::printScheduleProcess())
-          DEBUG_PRINT(std::cerr << "\n");
-      }
-    }
-  }
-  if (ModuloScheduling::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 = std::max((int) tempII, ResII);
-  }
-  return ResII;
 }
 
+void ModuloSchedGraph::MOB() {
 
-
-/*
-  dump the basicblock
-*/
-
-void 
-ModuloSchedGraph::dump(const BasicBlock * bb){
-  
-  DEBUG_PRINT(std::cerr << "dumping basic block:");
-  DEBUG_PRINT(std::cerr << (bb->hasName()? bb->getName() : "block")
-	      << " (" << bb << ")" << "\n");
-  
 }
 
-/*
-  dump the basicblock to ostream os
-*/
+void ModuloSchedGraph::ComputeDepth() {
 
-void 
-ModuloSchedGraph::dump(const BasicBlock * bb, std::ostream & os){
-
-  os << "dumping basic block:";
-  os << (bb->hasName()? bb->getName() : "block")
-      << " (" << bb << ")" << "\n";
 }
 
-/*
-  dump the graph
-*/
-
-void ModuloSchedGraph::dump() const
-{
-  DEBUG_PRINT(std::cerr << " ModuloSchedGraph for basic Blocks:");
-
-  DEBUG_PRINT(std::cerr << (bb->hasName()? bb->getName() : "block")
-	<< " (" << bb << ")" <<  "");
-
-  DEBUG_PRINT(std::cerr << "\n\n    Actual Root nodes : ");
-  for (unsigned i = 0, N = graphRoot->outEdges.size(); i < N; i++)
-    DEBUG_PRINT(std::cerr << graphRoot->outEdges[i]->getSink()->getNodeId()
-          << ((i == N - 1) ? "" : ", "));
-
-  DEBUG_PRINT(std::cerr << "\n    Graph Nodes:\n");
+void  ModuloSchedGraph::ComputeHeight() {
 
-  unsigned numNodes = bb->size();
-  for (unsigned i = 2; i < numNodes + 2; i++) {
-    ModuloSchedGraphNode *node = getNode(i);
-    DEBUG_PRINT(std::cerr << "\n" << *node);
-  }
-
-  DEBUG_PRINT(std::cerr << "\n");
 }
 
-
-/*
-  dump all node property
-*/
-
-void ModuloSchedGraph::dumpNodeProperty() const
-{
-
-  unsigned numNodes = bb->size();
-  for (unsigned i = 2; i < numNodes + 2; i++) {
-    ModuloSchedGraphNode *node = getNode(i);
-    DEBUG_PRINT(std::cerr << "NodeId " << node->getNodeId() << "\t");
-    DEBUG_PRINT(std::cerr << "ASAP " << node->getASAP() << "\t");
-    DEBUG_PRINT(std::cerr << "ALAP " << node->getALAP() << "\t");
-    DEBUG_PRINT(std::cerr << "mov " << node->getMov() << "\t");
-    DEBUG_PRINT(std::cerr << "depth " << node->getDepth() << "\t");
-    DEBUG_PRINT(std::cerr << "height " << node->getHeight() << "\t\n");
-  }
+void ModuloSchedGraphSet::addGraph(ModuloSchedGraph *graph) {
+  assert(graph!=NULL && "Graph for BasicBlock is null");
+  Graphs.push_back(graph);
 }
 
 
+ModuloSchedGraphSet::ModuloSchedGraphSet(const Function *F, 
+					 const TargetMachine &targ) 
+  : function(F) {
 
-
-/************member functions for ModuloSchedGraphSet**************/
-
-/*
-  constructor
-*/
-
-ModuloSchedGraphSet::ModuloSchedGraphSet(const Function *function,
-                                         const TargetMachine &target)
-:  method(function){
-  
-  buildGraphsForMethod(method, target);
-
+  //Create graph for each BB in this function
+  for (Function::const_iterator BI = F->begin(); BI != F->end(); ++BI)
+    addGraph(new ModuloSchedGraph(BI, targ));
 }
 
-/*
-  destructor
-*/
-
-
 ModuloSchedGraphSet::~ModuloSchedGraphSet(){
   
   //delete all the graphs
-  for (iterator I = begin(), E = end(); I != E; ++I)
-    delete *I;
 }
 
-
-
-/*
-  build graph for each basicblock in this method
-*/
-
-void 
-ModuloSchedGraphSet::buildGraphsForMethod(const Function *F,
-					  const TargetMachine &target){
-  
-  for (Function::const_iterator BI = F->begin(); BI != F->end(); ++BI){
-    const BasicBlock* local_bb;
-    
-    local_bb=BI;
-    addGraph(new ModuloSchedGraph((BasicBlock*)local_bb, target));
-  }
-  
-}
-
-/*
-  dump the graph set
-*/
-
-void 
-ModuloSchedGraphSet::dump() const{
-  
-  DEBUG_PRINT(std::cerr << " ====== ModuloSched graphs for function `" << 
-	      method->getName() << "' =========\n\n");
-  for (const_iterator I = begin(); I != end(); ++I)
-    (*I)->dump();
-  
-  DEBUG_PRINT(std::cerr << "\n=========End graphs for function `" << method->getName()
-	      << "' ==========\n\n");
-}
-
-
-
-
-/********************misc functions***************************/
-
-
-/*
-  dump the input basic block
-*/
-
-static void 
-dumpBasicBlock(const BasicBlock * bb){
-  
-  DEBUG_PRINT(std::cerr << "dumping basic block:");
-  DEBUG_PRINT(std::cerr << (bb->hasName()? bb->getName() : "block")
-	      << " (" << bb << ")" << "\n");
-}
-
-/*
-  dump the input node
-*/
-
-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;
-}
diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedGraph.h b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedGraph.h
index 2abd448fcd..3404a747ee 100644
--- a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedGraph.h
+++ b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedGraph.h
@@ -1,367 +1,101 @@
 //===- ModuloSchedGraph.h - Modulo Scheduling Graph and Set -*- C++ -*-----===//
-//
-// This header defines the primative classes that make up a data structure
-// graph.
+// 
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_CODEGEN_MODULO_SCHED_GRAPH_H
-#define LLVM_CODEGEN_MODULO_SCHED_GRAPH_H
+#ifndef LLVM_MODULO_SCHED_GRAPH_H
+#define LLVM_MODULO_SCHED_GRAPH_H
 
 #include "llvm/Instruction.h"
+#include "llvm/CodeGen/SchedGraphCommon.h"
 #include "llvm/Target/TargetMachine.h"
-#include "llvm/Target/TargetInstrInfo.h"
-#include "Support/GraphTraits.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Function.h"
 #include "Support/hash_map"
-#include "../InstrSched/SchedGraphCommon.h"
-#include <iostream>
+#include <vector>
 
-//===----------------------------------------------------------------------===//
-// ModuloSchedGraphNode - Implement a data structure based on the
-// SchedGraphNodeCommon this class stores informtion needed later to order the
-// nodes in modulo scheduling
-//
-class ModuloSchedGraphNode:public SchedGraphNodeCommon {
-private:
-  // the corresponding instruction 
-  const Instruction *inst;
 
-  // whether this node's property(ASAP,ALAP, ...) has been computed
-  bool propertyComputed;
+class ModuloSchedGraphNode : public SchedGraphNodeCommon {
 
-  // ASAP: the earliest time the node could be scheduled
-  // ALAP: the latest time the node couldbe scheduled
-  // depth: the depth of the node
-  // height: the height of the node
-  // mov: the mobility function, computed as ALAP - ASAP
-  // scheTime: the scheduled time if this node has been scheduled 
-  // earlyStart: the earliest time to be tried to schedule the node
-  // lateStart: the latest time to be tried to schedule the node
-  int ASAP, ALAP, depth, height, mov;
-  int schTime;
-  int earlyStart, lateStart;
+  const Instruction *Inst;  //Node's Instruction
+  unsigned Earliest;        //ASAP, or earliest time to be scheduled
+  unsigned Latest;          //ALAP, or latested time to be scheduled
+  unsigned Depth;           //Max Distance from node to the root
+  unsigned Height;          //Max Distance from node to leaf
+  unsigned Mobility;        //MOB, number of time slots it can be scheduled
+  const TargetMachine &Target; //Target information.
 
 public:
-
-  //get the instruction
-  const Instruction *getInst() const {
-    return inst;
-  }
-  //get the instruction op-code name
-  const char *getInstOpcodeName() const {
-    return inst->getOpcodeName();
-  }
-  //get the instruction op-code
-  const unsigned getInstOpcode() const {
-    return inst->getOpcode();
-  }
-
-  //return whether the node is NULL
-  bool isNullNode() const {
-    return (inst == NULL);
-  }
-  //return whether the property of the node has been computed
-  bool getPropertyComputed() {
-    return propertyComputed;
-  }
-  //set the propertyComputed
-  void setPropertyComputed(bool _propertyComputed) {
-    propertyComputed = _propertyComputed;
-  }
+  ModuloSchedGraphNode(unsigned ID, int index, const Instruction *inst, 
+		       const TargetMachine &target);
   
-  //get the corresponding property
-  int getASAP() {
-    return ASAP;
-  }
-  int getALAP() {
-    return ALAP;
-  }
-  int getMov() {
-    return mov;
-  }
-  int getDepth() {
-    return depth;
-  }
-  int getHeight() {
-    return height;
-  }
-  int getSchTime() {
-    return schTime;
-  }
-  int getEarlyStart() {
-    return earlyStart;
-  }
-  int getLateStart() {
-    return lateStart;
-  }
-  void setEarlyStart(int _earlyStart) {
-    earlyStart = _earlyStart;
-  }
-  void setLateStart(int _lateStart) {
-    lateStart = _lateStart;
-  }
-  void setSchTime(int _time) {
-    schTime = _time;
-  }
-
-private:
-  friend class ModuloSchedGraph;
-  friend class SchedGraphNode;
-
-  //constructor:
-  //nodeId: the node id, unique within the each BasicBlock
-  //_bb: which BasicBlock the corresponding instruction belongs to 
-  //_inst: the corresponding instruction
-  //indexInBB: the corresponding instruction's index in the BasicBlock
-  //target: the targetMachine
-  ModuloSchedGraphNode(unsigned int _nodeId,
-                       const BasicBlock * _bb,
-                       const Instruction * _inst,
-                       int indexInBB, const TargetMachine &target);
-
+  void print(std::ostream &os) const;
+  const Instruction* getInst() { return Inst; }
+  unsigned getEarliest() { return Earliest; }
+  unsigned getLatest() { return Latest; }
+  unsigned getDepth() { return Depth; }
+  unsigned getHeight() { return Height; }
+  unsigned getMobility() { return Mobility; }
   
-  friend std::ostream & operator<<(std::ostream & os,
-                                   const ModuloSchedGraphNode & edge);
-
-};
-
-//FIXME: these two value should not be used
-#define MAXNODE 100
-#define MAXCC   100
-
-//===----------------------------------------------------------------------===//
-/// ModuloSchedGraph- the data structure to store dependence between nodes
-/// it catches data dependence and constrol dependence
-/// 
-class ModuloSchedGraph :
-  public SchedGraphCommon,
-  protected hash_map<const Instruction*,ModuloSchedGraphNode*> {
-
-private:
-
-  BasicBlock* bb;
-  
-  //iteration Interval
-  int MII;
-
-  //target machine
-  const TargetMachine & target;
+  void setEarliest(unsigned early) { Earliest = early; }
+  void setLatest(unsigned late) { Latest = late; }
+  void setDepth(unsigned depth) { Depth = depth; }
+  void setHeight(unsigned height) { Height = height; }
+  void setMobility(unsigned mob) { Mobility = mob; }
 
-  //the circuits in the dependence graph
-  unsigned circuits[MAXCC][MAXNODE];
 
-  //the order nodes
-  std::vector<ModuloSchedGraphNode*> oNodes;
-
-  typedef std::vector<ModuloSchedGraphNode*> NodeVec;
-
-  //the function to compute properties
-  void computeNodeASAP(const BasicBlock * in_bb);
-  void computeNodeALAP(const BasicBlock * in_bb);
-  void computeNodeMov(const BasicBlock *  in_bb);
-  void computeNodeDepth(const BasicBlock * in_bb);
-  void computeNodeHeight(const BasicBlock * in_bb);
-
-  //the function to compute node property
-  void computeNodeProperty(const BasicBlock * in_bb);
-
-  //the function to sort nodes
-  void orderNodes();
-
-  //add the resource usage 
-void addResourceUsage(std::vector<std::pair<int,int> > &, int);
-
-  //debug functions:
-  //dump circuits
-  void dumpCircuits();
-  //dump the input set of nodes
-  void dumpSet(std::vector<ModuloSchedGraphNode*> set);
-  //dump the input resource usage table  
-  void dumpResourceUsage(std::vector<std::pair<int,int> > &);
-
-public:
-  //help functions
-
-  //get the maxium the delay between two nodes
-  SchedGraphEdge *getMaxDelayEdge(unsigned srcId, unsigned sinkId);
-
-  //FIXME:
-  //get the predessor Set of the set
-  NodeVec predSet(NodeVec set, unsigned, unsigned);
-  NodeVec predSet(NodeVec set);
-
-  //get the predessor set of the node
-  NodeVec predSet(ModuloSchedGraphNode *node, unsigned, unsigned);
-  NodeVec predSet(ModuloSchedGraphNode *node);
-
-  //get the successor set of the set
-  NodeVec succSet(NodeVec set, unsigned, unsigned);
-  NodeVec succSet(NodeVec set);
-
-  //get the succssor set of the node
-  NodeVec succSet(ModuloSchedGraphNode *node, unsigned, unsigned);
-  NodeVec succSet(ModuloSchedGraphNode *node);
+};
 
-  //return the uniton of the two vectors
-  NodeVec vectorUnion(NodeVec set1, NodeVec set2);
+class ModuloSchedGraph : public SchedGraphCommon {
   
-  //return the consjuction of the two vectors
-  NodeVec vectorConj(NodeVec set1, NodeVec set2);
-
-  //return all nodes in  set1 but not  set2
-  NodeVec vectorSub(NodeVec set1, NodeVec set2);
-
-  typedef hash_map<const Instruction*,ModuloSchedGraphNode*> map_base;
+  const BasicBlock *BB; //The Basic block this graph represents
+  const TargetMachine &Target;
+  hash_map<const Instruction*, ModuloSchedGraphNode*> GraphMap;
 
-public:
-  using map_base::iterator;
-  using map_base::const_iterator;
-
-public:
-
-  //get target machine
-  const TargetMachine & getTarget() {
-    return target;
-  }
-
-  //get the basic block
-  BasicBlock* getBasicBlock() const {
-    return bb;
-  }
-
-
-  //get the iteration interval
-  const int getMII() {
-    return MII;
-  }
-
-  //get the ordered nodes
-  const NodeVec & getONodes() {
-    return oNodes;
-  }
-
-  //get the number of nodes (including the root and leaf)
-  //note: actually root and leaf is not used
-  const unsigned int getNumNodes() const {
-    return size() + 2;
-  }
-
-  //return wether the BasicBlock 'bb' contains a loop
-  bool isLoop(const BasicBlock *bb);
-
-  //return the node for the input instruction
-  ModuloSchedGraphNode *getGraphNodeForInst(const Instruction *inst) const {
-    const_iterator onePair = this->find(inst);
-    return (onePair != this->end()) ? (*onePair).second : NULL;
-  }
-
-  // Debugging support
-  //dump the graph
-  void dump() const;
-
-  // dump the basicBlock
-  void dump(const BasicBlock *bb);
-
-  //dump the basicBlock into 'os' stream
-  void dump(const BasicBlock *bb, std::ostream &os);
-
-  //dump the node property
-  void dumpNodeProperty() const;
-  
-private:
-  friend class ModuloSchedGraphSet;     //give access to ctor
+  void buildNodesForBB();
 
 public:
-  ModuloSchedGraph(BasicBlock * in_bb, 
-		   const TargetMachine & in_target)
-    :SchedGraphCommon(), bb(in_bb),target(in_target)
-  {
-    buildGraph(target);
-  }
-
-  ~ModuloSchedGraph() {
-    for (const_iterator I = begin(); I != end(); ++I)
-      delete I->second;
-  }
-
-  // Unorder iterators
-  // return values are pair<const Instruction*, ModuloSchedGraphNode*>
-  using map_base::begin;
-  using map_base::end;
-
-  void addHash(const Instruction *inst,
-	       ModuloSchedGraphNode *node){
-    
-    assert((*this)[inst] == NULL);
-    (*this)[inst] = node;
-    
-  }
-
-  // Graph builder
-  ModuloSchedGraphNode *getNode(const unsigned nodeId) const;
-
-  // Build the graph from the basicBlock
-  void buildGraph(const TargetMachine &target);
-
-  // Build nodes for BasicBlock
-  void buildNodesforBB(const TargetMachine &target,
-                       const BasicBlock *bb);
-
-  //find definitiona and use information for all nodes
-  void findDefUseInfoAtInstr(const TargetMachine &target,
-                             ModuloSchedGraphNode *node,
-                             NodeVec &memNode,
-                             RegToRefVecMap &regToRefVecMap,
-                             ValueToDefVecMap &valueToDefVecMap);
-
-  //add def-use edge
-  void addDefUseEdges(const BasicBlock *bb);
-
-  //add control dependence edges
-  void addCDEdges(const BasicBlock *bb);
-
-  //add memory dependence dges
-  void addMemEdges(const BasicBlock *bb);
-
-  //computer source restrictoin II
-  int computeResII(const BasicBlock *bb);
-
-  //computer recurrence II
-  int computeRecII(const BasicBlock *bb);
+  typedef hash_map<const Instruction*, 
+		   ModuloSchedGraphNode*>::iterator iterator;
+  typedef hash_map<const Instruction*, 
+		   ModuloSchedGraphNode*>::const_iterator const_iterator;
+
+
+  ModuloSchedGraph(const BasicBlock *bb, const TargetMachine &targ);
+
+  const BasicBlock* getBB() { return BB; }
+  void setBB(BasicBlock *bb) { BB = bb; }
+  unsigned size() { return GraphMap.size(); }
+  void addNode(const Instruction *I, ModuloSchedGraphNode *node);
+  void ASAP(); //Calculate earliest schedule time for all nodes in graph.
+  void ALAP(); //Calculate latest schedule time for all nodes in graph.
+  void MOB(); //Calculate mobility for all nodes in the graph.
+  void ComputeDepth(); //Compute depth of each node in graph
+  void ComputeHeight(); //Computer height of each node in graph
+  void addDepEdges(); //Add Dependencies
+  iterator find(const Instruction *I) { return GraphMap.find(I); }
 };
 
-//==================================-
-// Graph set
 
-class ModuloSchedGraphSet : public std::vector<ModuloSchedGraph*> {
-private:
-  const Function *method;
-
-public:
-  typedef std::vector<ModuloSchedGraph*> baseVector;
-  using baseVector::iterator;
-  using baseVector::const_iterator;
+class ModuloSchedGraphSet {
+  
+  const Function *function; //Function this set of graphs represent.
+  std::vector<ModuloSchedGraph*> Graphs;
 
 public:
-  ModuloSchedGraphSet(const Function *function, const TargetMachine &target);
+  typedef std::vector<ModuloSchedGraph*>::iterator iterator;
+  typedef std::vector<ModuloSchedGraph*>::const_iterator const_iterator;
+ 
+  iterator begin() { return Graphs.begin(); }
+  iterator end() { return Graphs.end(); }
+ 
+  ModuloSchedGraphSet(const Function *func, const TargetMachine &target);
   ~ModuloSchedGraphSet();
 
-  // Iterators
-  using baseVector::begin;
-  using baseVector::end;
-
-  // Debugging support
+  void addGraph(ModuloSchedGraph *graph);
   void dump() const;
 
-private:
-  void addGraph(ModuloSchedGraph *graph) {
-    assert(graph != NULL);
-    this->push_back(graph);
-  }
 
-  // Graph builder
-  void buildGraphsForMethod(const Function *F,
-                            const TargetMachine &target);
 };
 
 #endif
diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp
index 49f4246c02..bad3e97e48 100644
--- a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp
+++ b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp
@@ -1,983 +1,35 @@
-//===- ModuloScheduling.cpp - Modulo Software Pipelining ------------------===//
+//===-- ModuloScheduling.cpp - Software Pipeling Approach - SMS --*- C++ -*--=//
 //
-// Implements the llvm/CodeGen/ModuloScheduling.h interface
+// The is a software pipelining pass based on the Swing Modulo Scheduling
+// alogrithm (SMS).
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/BasicBlock.h"
-#include "llvm/Constants.h"
-#include "llvm/iTerminators.h"
-#include "llvm/iPHINode.h"
-#include "llvm/CodeGen/MachineInstr.h"
-#include "llvm/CodeGen/MachineCodeForInstruction.h"
-#include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/CodeGen/InstrSelection.h"
-#include "llvm/Target/TargetSchedInfo.h"
-#include "llvm/Target/TargetMachine.h"
-#include "Support/CommandLine.h"
-#include "Support/Statistic.h"
 #include "ModuloSchedGraph.h"
-#include "ModuloScheduling.h"
-#include <algorithm>
-#include <fstream>
 
-//************************************************************
-// printing Debug information
-// ModuloSchedDebugLevel stores the value of debug level
-// modsched_os is the ostream to dump debug information, which is written into
-// the file 'moduloSchedDebugInfo.output'
-// see ModuloSchedulingPass::runOnFunction()
-//************************************************************
+#include "llvm/Pass.h"
+#include "llvm/Function.h"
 
-ModuloSchedDebugLevel_t ModuloSchedDebugLevel;
-
-cl::opt<ModuloSchedDebugLevel_t,true>
-SDL_opt("modsched", cl::Hidden, cl::location(ModuloSchedDebugLevel),
-	cl::desc("enable modulo scheduling debugging information"),
-	cl::values(clEnumValN(ModuloSchedDebugLevel_NoDebugInfo,
-			      "none", "disable debug output"),
-		   clEnumValN(ModuloSchedDebugLevel_PrintSchedule,
-			      "psched", "print original and new schedule"),
-		   clEnumValN(ModuloSchedDebugLevel_PrintScheduleProcess,
-			      "pschedproc",
-			      "print how the new schdule is produced"),
-		   0));
-
-// Computes the schedule and inserts epilogue and prologue
-//
-void 
-ModuloScheduling::instrScheduling(){
-
-
-  if (ModuloScheduling::printScheduleProcess())
-    DEBUG_PRINT(std::cerr << "************ computing modulo schedule ***********\n");
-
-  const TargetSchedInfo & msi = target.getSchedInfo();
-
-  //number of issue slots in the in each cycle
-  int numIssueSlots = msi.maxNumIssueTotal;
-
-  //compute the schedule
-  bool success = false;
-  while (!success) {
-    //clear memory from the last round and initialize if necessary
-    clearInitMem(msi);
-
-    //compute schedule and coreSchedule with the current II
-    success = computeSchedule();
-
-    if (!success) {
-      II++;
-      if (ModuloScheduling::printScheduleProcess())
-        DEBUG_PRINT(std::cerr << "increase II  to " << II << "\n");
-    }
-  }
-
-  //print the final schedule
-  dumpFinalSchedule();
-  
-  //the schedule has been computed
-  //create epilogue, prologue and kernel BasicBlock
-
-  //find the successor for this BasicBlock
-  BasicBlock *succ_bb = getSuccBB(bb);
-
-  //print the original BasicBlock if necessary
-  if (ModuloScheduling::printSchedule()) {
-    DEBUG_PRINT(std::cerr << "dumping the orginal block\n");
-    graph.dump(bb);
-  }
-  //construction of prologue, kernel and epilogue
-  
-  /*
-  BasicBlock *kernel = bb->splitBasicBlock(bb->begin());
-  BasicBlock *prologue = bb;
-  BasicBlock *epilogue = kernel->splitBasicBlock(kernel->begin());
-  */
-
-  // Construct prologue
-  /*constructPrologue(prologue);*/
-
-  // Construct kernel
-  
-  /*constructKernel(prologue, kernel, epilogue);*/
-
-  // Construct epilogue
-
-  /*constructEpilogue(epilogue, succ_bb);*/
+namespace {
   
-  //print the BasicBlocks if necessary
-//    if (0){
-//      DEBUG_PRINT(std::cerr << "dumping the prologue block:\n");
-//      graph.dump(prologue);
-//      DEBUG_PRINT(std::cerr << "dumping the kernel block\n");
-//      graph.dump(kernel);
-//      DEBUG_PRINT(std::cerr << "dumping the epilogue block\n");
-//      graph.dump(epilogue);
-//    }
-
-}
-
-
-// Clear memory from the last round and initialize if necessary
-//
-
-void 
-ModuloScheduling::clearInitMem(const TargetSchedInfo & msi){
-
-  unsigned numIssueSlots = msi.maxNumIssueTotal;
-  // clear nodeScheduled from the last round
-  if (ModuloScheduling::printScheduleProcess()) {
-    DEBUG_PRINT(std::cerr << "***** new round  with II= " << II << " ***********\n");
-    DEBUG_PRINT(std::cerr <<
-        " ************clear the vector nodeScheduled*************\n");
-  }
-  nodeScheduled.clear();
-
-  // clear resourceTable from the last round and reset it 
-  resourceTable.clear();
-  for (unsigned i = 0; i < II; ++i)
-    resourceTable.push_back(msi.resourceNumVector);
-
-  // clear the schdule and coreSchedule from the last round 
-  schedule.clear();
-  coreSchedule.clear();
-
-  // create a coreSchedule of size II*numIssueSlots
-  // each entry is NULL
-  while (coreSchedule.size() < II) {
-    std::vector < ModuloSchedGraphNode * >*newCycle =
-        new std::vector < ModuloSchedGraphNode * >();
-    for (unsigned k = 0; k < numIssueSlots; ++k)
-      newCycle->push_back(NULL);
-    coreSchedule.push_back(*newCycle);
-  }
-}
-
-// Compute schedule and coreSchedule with the current II
-//
-bool 
-ModuloScheduling::computeSchedule(){
-
-
-  if (ModuloScheduling::printScheduleProcess())
-    DEBUG_PRINT(std::cerr << "start to compute schedule\n");
-
-  // Loop over the ordered nodes
-  for (NodeVec::const_iterator I = oNodes.begin(); I != oNodes.end(); ++I) {
-    // Try to schedule for node I
-    if (ModuloScheduling::printScheduleProcess())
-      dumpScheduling();
-    ModuloSchedGraphNode *node = *I;
-
-    // Compute whether this node has successor(s)
-    bool succ = true;
-
-    // Compute whether this node has predessor(s)
-    bool pred = true;
-
-    NodeVec schSucc = graph.vectorConj(nodeScheduled, graph.succSet(node));
-    if (schSucc.empty())
-      succ = false;
-    NodeVec schPred = graph.vectorConj(nodeScheduled, graph.predSet(node));
-    if (schPred.empty())
-      pred = false;
-
-    //startTime: the earliest time we will try to schedule this node
-    //endTime: the latest time we will try to schedule this node
-    int startTime, endTime;
-
-    //node's earlyStart: possible earliest time to schedule this node
-    //node's lateStart: possible latest time to schedule this node
-    node->setEarlyStart(-1);
-    node->setLateStart(9999);
-
-    //this node has predessor but no successor
-    if (!succ && pred) {
-      // This node's earlyStart is it's predessor's schedule time + the edge
-      // delay - the iteration difference* II
-      for (unsigned i = 0; i < schPred.size(); i++) {
-        ModuloSchedGraphNode *predNode = schPred[i];
-        SchedGraphEdge *edge =
-            graph.getMaxDelayEdge(predNode->getNodeId(),
-                                  node->getNodeId());
-        int temp =
-            predNode->getSchTime() + edge->getMinDelay() -
-            edge->getIteDiff() * II;
-        node->setEarlyStart(std::max(node->getEarlyStart(), temp));
-      }
-      startTime = node->getEarlyStart();
-      endTime = node->getEarlyStart() + II - 1;
-    }
-    // This node has a successor but no predecessor
-    if (succ && !pred) {
-      for (unsigned i = 0; i < schSucc.size(); ++i) {
-        ModuloSchedGraphNode *succNode = schSucc[i];
-        SchedGraphEdge *edge =
-            graph.getMaxDelayEdge(succNode->getNodeId(),
-                                  node->getNodeId());
-        int temp =
-            succNode->getSchTime() - edge->getMinDelay() +
-            edge->getIteDiff() * II;
-        node->setLateStart(std::min(node->getEarlyStart(), temp));
-      }
-      startTime = node->getLateStart() - II + 1;
-      endTime = node->getLateStart();
-    }
-    // This node has both successors and predecessors
-    if (succ && pred) {
-      for (unsigned i = 0; i < schPred.size(); ++i) {
-        ModuloSchedGraphNode *predNode = schPred[i];
-        SchedGraphEdge *edge =
-            graph.getMaxDelayEdge(predNode->getNodeId(),
-                                  node->getNodeId());
-        int temp =
-            predNode->getSchTime() + edge->getMinDelay() -
-            edge->getIteDiff() * II;
-        node->setEarlyStart(std::max(node->getEarlyStart(), temp));
-      }
-      for (unsigned i = 0; i < schSucc.size(); ++i) {
-        ModuloSchedGraphNode *succNode = schSucc[i];
-        SchedGraphEdge *edge =
-            graph.getMaxDelayEdge(succNode->getNodeId(),
-                                  node->getNodeId());
-        int temp =
-            succNode->getSchTime() - edge->getMinDelay() +
-            edge->getIteDiff() * II;
-        node->setLateStart(std::min(node->getEarlyStart(), temp));
-      }
-      startTime = node->getEarlyStart();
-      endTime = std::min(node->getLateStart(),
-                         node->getEarlyStart() + ((int) II) - 1);
-    }
-    //this node has no successor or predessor
-    if (!succ && !pred) {
-      node->setEarlyStart(node->getASAP());
-      startTime = node->getEarlyStart();
-      endTime = node->getEarlyStart() + II - 1;
-    }
-    //try to schedule this node based on the startTime and endTime
-    if (ModuloScheduling::printScheduleProcess())
-      DEBUG_PRINT(std::cerr << "scheduling the node " << (*I)->getNodeId() << "\n");
-
-    bool success =
-        this->ScheduleNode(node, startTime, endTime, nodeScheduled);
-    if (!success)
-      return false;
-  }
-  return true;
-}
-
-
-// Get the successor of the BasicBlock
-//
-BasicBlock *
-ModuloScheduling::getSuccBB(BasicBlock *bb){
-
-  BasicBlock *succ_bb;
-  for (unsigned i = 0; i < II; ++i)
-    for (unsigned j = 0; j < coreSchedule[i].size(); ++j)
-      if (coreSchedule[i][j]) {
-        const Instruction *ist = coreSchedule[i][j]->getInst();
-
-        //we can get successor from the BranchInst instruction
-        //assume we only have one successor (besides itself) here
-        if (BranchInst::classof(ist)) {
-          BranchInst *bi = (BranchInst *) ist;
-          assert(bi->isConditional() &&
-                 "the branchInst is not a conditional one");
-          assert(bi->getNumSuccessors() == 2
-                 && " more than two successors?");
-          BasicBlock *bb1 = bi->getSuccessor(0);
-          BasicBlock *bb2 = bi->getSuccessor(1);
-          assert((bb1 == bb || bb2 == bb) &&
-                 " None of its successors is itself?");
-          if (bb1 == bb)
-            succ_bb = bb2;
-          else
-            succ_bb = bb1;
-          return succ_bb;
-        }
-      }
-  assert(0 && "NO Successor?");
-  return NULL;
-}
-
-
-// Get the predecessor of the BasicBlock
-//
-BasicBlock *
-ModuloScheduling::getPredBB(BasicBlock *bb){
-
-  BasicBlock *pred_bb;
-  for (unsigned i = 0; i < II; ++i)
-    for (unsigned j = 0; j < coreSchedule[i].size(); ++j)
-      if (coreSchedule[i][j]) {
-        const Instruction *ist = coreSchedule[i][j]->getInst();
-
-        //we can get predecessor from the PHINode instruction
-        //assume we only have one predecessor (besides itself) here
-        if (PHINode::classof(ist)) {
-          PHINode *phi = (PHINode *) ist;
-          assert(phi->getNumIncomingValues() == 2 &&
-                 " the number of incoming value is not equal to two? ");
-          BasicBlock *bb1 = phi->getIncomingBlock(0);
-          BasicBlock *bb2 = phi->getIncomingBlock(1);
-          assert((bb1 == bb || bb2 == bb) &&
-                 " None of its predecessor is itself?");
-          if (bb1 == bb)
-            pred_bb = bb2;
-          else
-            pred_bb = bb1;
-          return pred_bb;
-        }
-      }
-  assert(0 && " no predecessor?");
-  return NULL;
-}
-
-
-// Construct the prologue
-//
-void 
-ModuloScheduling::constructPrologue(BasicBlock *prologue){
-
-  InstListType & prologue_ist = prologue->getInstList();
-  vvNodeType & tempSchedule_prologue =
-      *(new std::vector<std::vector<ModuloSchedGraphNode*> >(schedule));
-
-  //compute the schedule for prologue
-  unsigned round = 0;
-  unsigned scheduleSize = schedule.size();
-  while (round < scheduleSize / II) {
-    round++;
-    for (unsigned i = 0; i < scheduleSize; ++i) {
-      if (round * II + i >= scheduleSize)
-        break;
-      for (unsigned j = 0; j < schedule[i].size(); ++j) {
-        if (schedule[i][j]) {
-          assert(tempSchedule_prologue[round * II + i][j] == NULL &&
-                 "table not consitent with core table");
-          // move the schedule one iteration ahead and overlap with the original
-          tempSchedule_prologue[round * II + i][j] = schedule[i][j];
-        }
-      }
-    }
-  }
-
-  // Clear the clone memory in the core schedule instructions
-  clearCloneMemory();
-
-  // Fill in the prologue
-  for (unsigned i = 0; i < ceil(1.0 * scheduleSize / II - 1) * II; ++i)
-    for (unsigned j = 0; j < tempSchedule_prologue[i].size(); ++j)
-      if (tempSchedule_prologue[i][j]) {
-
-        //get the instruction
-        Instruction *orn =
-            (Instruction *) tempSchedule_prologue[i][j]->getInst();
-
-        //made a clone of it
-        Instruction *cln = cloneInstSetMemory(orn);
-
-        //insert the instruction
-        prologue_ist.insert(prologue_ist.back(), cln);
-
-        //if there is PHINode in the prologue, the incoming value from itself
-        //should be removed because it is not a loop any longer
-        if (PHINode::classof(cln)) {
-          PHINode *phi = (PHINode *) cln;
-          phi->removeIncomingValue(phi->getParent());
-        }
-      }
-}
-
-
-// Construct the kernel BasicBlock
-//
-void 
-ModuloScheduling::constructKernel(BasicBlock *prologue,
-                                       BasicBlock *kernel,
-                                       BasicBlock *epilogue){
-
-  //*************fill instructions in the kernel****************
-  InstListType & kernel_ist = kernel->getInstList();
-  BranchInst *brchInst;
-  PHINode *phiInst, *phiCln;
-
-  for (unsigned i = 0; i < coreSchedule.size(); ++i)
-    for (unsigned j = 0; j < coreSchedule[i].size(); ++j)
-      if (coreSchedule[i][j]) {
-
-        // Take care of branch instruction differently with normal instructions
-        if (BranchInst::classof(coreSchedule[i][j]->getInst())) {
-          brchInst = (BranchInst *) coreSchedule[i][j]->getInst();
-          continue;
-        }
-        // Take care of PHINode instruction differently with normal instructions
-        if (PHINode::classof(coreSchedule[i][j]->getInst())) {
-          phiInst = (PHINode *) coreSchedule[i][j]->getInst();
-          Instruction *cln = cloneInstSetMemory(phiInst);
-          kernel_ist.insert(kernel_ist.back(), cln);
-          phiCln = (PHINode *) cln;
-          continue;
-        }
-        //for normal instructions: made a clone and insert it in the kernel_ist
-        Instruction *cln =
-            cloneInstSetMemory((Instruction *) coreSchedule[i][j]->
-                               getInst());
-        kernel_ist.insert(kernel_ist.back(), cln);
-      }
-  // The two incoming BasicBlock for PHINode is the prologue and the kernel
-  // (itself)
-  phiCln->setIncomingBlock(0, prologue);
-  phiCln->setIncomingBlock(1, kernel);
-
-  // The incoming value for the kernel (itself) is the new value which is
-  // computed in the kernel
-  Instruction *originalVal = (Instruction *) phiInst->getIncomingValue(1);
-  phiCln->setIncomingValue(1, originalVal->getClone());
-
-  // Make a clone of the branch instruction and insert it in the end
-  BranchInst *cln = (BranchInst *) cloneInstSetMemory(brchInst);
-  kernel_ist.insert(kernel_ist.back(), cln);
-
-  // delete the unconditional branch instruction, which is generated when
-  // splitting the basicBlock
-  kernel_ist.erase(--kernel_ist.end());
-
-  // set the first successor to itself
-  cln->setSuccessor(0, kernel);
-  // set the second successor to eiplogue
-  cln->setSuccessor(1, epilogue);
-
-  //*****change the condition*******
-
-  //get the condition instruction
-  Instruction *cond = (Instruction *) cln->getCondition();
-
-  //get the condition's second operand, it should be a constant
-  Value *operand = cond->getOperand(1);
-  assert(ConstantSInt::classof(operand));
-
-  //change the constant in the condtion instruction
-  ConstantSInt *iteTimes =
-      ConstantSInt::get(operand->getType(),
-                        ((ConstantSInt *) operand)->getValue() - II + 1);
-  cond->setOperand(1, iteTimes);
-
-}
-
-
-// Construct the epilogue 
-//
-void 
-ModuloScheduling::constructEpilogue(BasicBlock *epilogue,
-                                         BasicBlock *succ_bb){
-
-  //compute the schedule for epilogue
-  vvNodeType &tempSchedule_epilogue =
-      *(new std::vector<std::vector<ModuloSchedGraphNode*> >(schedule));
-  unsigned scheduleSize = schedule.size();
-  int round = 0;
-  while (round < ceil(1.0 * scheduleSize / II) - 1) {
-    round++;
-    for (unsigned i = 0; i < scheduleSize; i++) {
-      if (i + round * II >= scheduleSize)
-        break;
-      for (unsigned j = 0; j < schedule[i].size(); j++)
-        if (schedule[i + round * II][j]) {
-          assert(tempSchedule_epilogue[i][j] == NULL
-                 && "table not consitant with core table");
-
-          //move the schdule one iteration behind and overlap
-          tempSchedule_epilogue[i][j] = schedule[i + round * II][j];
-        }
-    }
-  }
-
-  //fill in the epilogue
-  InstListType & epilogue_ist = epilogue->getInstList();
-  for (unsigned i = II; i < scheduleSize; i++)
-    for (unsigned j = 0; j < tempSchedule_epilogue[i].size(); j++)
-      if (tempSchedule_epilogue[i][j]) {
-        Instruction *inst =
-            (Instruction *) tempSchedule_epilogue[i][j]->getInst();
-
-        //BranchInst and PHINode should be treated differently
-        //BranchInst:unecessary, simly omitted
-        //PHINode: omitted
-        if (!BranchInst::classof(inst) && !PHINode::classof(inst)) {
-          //make a clone instruction and insert it into the epilogue
-          Instruction *cln = cloneInstSetMemory(inst);
-          epilogue_ist.push_front(cln);
-        }
-      }
-
-  //*************delete the original instructions****************//
-  //to delete the original instructions, we have to make sure their use is zero
-
-  //update original core instruction's uses, using its clone instread
-  for (unsigned i = 0; i < II; i++)
-    for (unsigned j = 0; j < coreSchedule[i].size(); j++) {
-      if (coreSchedule[i][j])
-        updateUseWithClone((Instruction *) coreSchedule[i][j]->getInst());
-    }
-
-  //erase these instructions
-  for (unsigned i = 0; i < II; i++)
-    for (unsigned j = 0; j < coreSchedule[i].size(); j++)
-      if (coreSchedule[i][j]) {
-        Instruction *ist = (Instruction *) coreSchedule[i][j]->getInst();
-        ist->getParent()->getInstList().erase(ist);
-      }
-
-
-
-  //finally, insert an unconditional branch instruction at the end
-  epilogue_ist.push_back(new BranchInst(succ_bb));
-
-}
-
-
-//------------------------------------------------------------------------------
-//this function replace the value(instruction) ist in other instructions with
-//its latest clone i.e. after this function is called, the ist is not used
-//anywhere and it can be erased.
-//------------------------------------------------------------------------------
-void 
-ModuloScheduling::updateUseWithClone(Instruction * ist){
-
-
-  while (ist->use_size() > 0) {
-    bool destroyed = false;
-
-    //other instruction is using this value ist
-    assert(Instruction::classof(*ist->use_begin()));
-    Instruction *inst = (Instruction *) (*ist->use_begin());
-
-    for (unsigned i = 0; i < inst->getNumOperands(); i++)
-      if (inst->getOperand(i) == ist && ist->getClone()) {
-        // if the instruction is TmpInstruction, simly delete it because it has
-        // no parent and it does not belongs to any BasicBlock
-        if (TmpInstruction::classof(inst)) {
-          delete inst;
-          destroyed = true;
-          break;
-        }
-
-        //otherwise, set the instruction's operand to the value's clone
-        inst->setOperand(i, ist->getClone());
-
-        //the use from the original value ist is destroyed
-        destroyed = true;
-        break;
-      }
-    if (!destroyed) {
-      //if the use can not be destroyed , something is wrong
-      inst->dump();
-      assert(0 && "this use can not be destroyed");
-    }
-  }
-
-}
-
-
-//********************************************************
-//this function clear all clone mememoy
-//i.e. set all instruction's clone memory to NULL
-//*****************************************************
-void 
-ModuloScheduling::clearCloneMemory(){
-
-  for (unsigned i = 0; i < coreSchedule.size(); i++)
-    for (unsigned j = 0; j < coreSchedule[i].size(); j++)
-      if (coreSchedule[i][j])
-        ((Instruction *) coreSchedule[i][j]->getInst())->clearClone();
-
-}
-
-
-//******************************************************************************
-// this function make a clone of the instruction orn the cloned instruction will
-// use the orn's operands' latest clone as its operands it is done this way
-// because LLVM is in SSA form and we should use the correct value
-//this fuction also update the instruction orn's latest clone memory
-//******************************************************************************
-Instruction *
-ModuloScheduling::cloneInstSetMemory(Instruction * orn){
-
-  // make a clone instruction
-  Instruction *cln = orn->clone();
-
-  // update the operands
-  for (unsigned k = 0; k < orn->getNumOperands(); k++) {
-    const Value *op = orn->getOperand(k);
-    if (Instruction::classof(op) && ((Instruction *) op)->getClone()) {
-      Instruction *op_inst = (Instruction *) op;
-      cln->setOperand(k, op_inst->getClone());
-    }
-  }
-
-  // update clone memory
-  orn->setClone(cln);
-  return cln;
-}
-
-
-
-bool 
-ModuloScheduling::ScheduleNode(ModuloSchedGraphNode * node,
-                                    unsigned start, unsigned end,
-                                    NodeVec & nodeScheduled){
-
-  const TargetSchedInfo & msi = target.getSchedInfo();
-  unsigned int numIssueSlots = msi.maxNumIssueTotal;
-
-  if (ModuloScheduling::printScheduleProcess())
-    DEBUG_PRINT(std::cerr << "startTime= " << start << " endTime= " << end << "\n");
-  bool isScheduled = false;
-  for (unsigned i = start; i <= end; i++) {
-    if (ModuloScheduling::printScheduleProcess())
-      DEBUG_PRINT(std::cerr << " now try cycle " << i << ":" << "\n");
-    for (unsigned j = 0; j < numIssueSlots; j++) {
-      unsigned int core_i = i % II;
-      unsigned int core_j = j;
-      if (ModuloScheduling::printScheduleProcess())
-        DEBUG_PRINT(std::cerr << "\t Trying slot " << j << "...........");
-      //check the resouce table, make sure there is no resource conflicts
-      const Instruction *instr = node->getInst();
-      MachineCodeForInstruction & tempMvec =
-          MachineCodeForInstruction::get(instr);
-      bool resourceConflict = false;
-      const TargetInstrInfo & mii = msi.getInstrInfo();
-
-      if (coreSchedule.size() < core_i + 1
-          || !coreSchedule[core_i][core_j]) {
-        //this->dumpResourceUsageTable();
-        int latency = 0;
-        for (unsigned k = 0; k < tempMvec.size(); k++) {
-          MachineInstr *minstr = tempMvec[k];
-          InstrRUsage rUsage = msi.getInstrRUsage(minstr->getOpCode());
-          std::vector < std::vector < resourceId_t > >resources
-              = rUsage.resourcesByCycle;
-          updateResourceTable(resources, i + latency);
-          latency += std::max(mii.minLatency(minstr->getOpCode()), 1);
-        }
-
-        //this->dumpResourceUsageTable();
-
-        latency = 0;
-        if (resourceTableNegative()) {
-
-          //undo-update the resource table
-          for (unsigned k = 0; k < tempMvec.size(); k++) {
-            MachineInstr *minstr = tempMvec[k];
-            InstrRUsage rUsage = msi.getInstrRUsage(minstr->getOpCode());
-            std::vector < std::vector < resourceId_t > >resources
-                = rUsage.resourcesByCycle;
-            undoUpdateResourceTable(resources, i + latency);
-            latency += std::max(mii.minLatency(minstr->getOpCode()), 1);
-          }
-          resourceConflict = true;
-        }
-      }
-      if (!resourceConflict && !coreSchedule[core_i][core_j]) {
-        if (ModuloScheduling::printScheduleProcess()) {
-          DEBUG_PRINT(std::cerr << " OK!" << "\n");
-          DEBUG_PRINT(std::cerr << "Node " << node->getNodeId() << " scheduled.\n");
-        }
-        //schedule[i][j]=node;
-        while (schedule.size() <= i) {
-          std::vector < ModuloSchedGraphNode * >*newCycle =
-              new std::vector < ModuloSchedGraphNode * >();
-          for (unsigned k = 0; k < numIssueSlots; k++)
-            newCycle->push_back(NULL);
-          schedule.push_back(*newCycle);
-        }
-        std::vector<ModuloSchedGraphNode*>::iterator startIterator;
-        startIterator = schedule[i].begin();
-        schedule[i].insert(startIterator + j, node);
-        startIterator = schedule[i].begin();
-        schedule[i].erase(startIterator + j + 1);
-
-        //update coreSchedule
-        //coreSchedule[core_i][core_j]=node;
-        while (coreSchedule.size() <= core_i) {
-          std::vector<ModuloSchedGraphNode*> *newCycle =
-              new std::vector<ModuloSchedGraphNode*>();
-          for (unsigned k = 0; k < numIssueSlots; k++)
-            newCycle->push_back(NULL);
-          coreSchedule.push_back(*newCycle);
-        }
-
-        startIterator = coreSchedule[core_i].begin();
-        coreSchedule[core_i].insert(startIterator + core_j, node);
-        startIterator = coreSchedule[core_i].begin();
-        coreSchedule[core_i].erase(startIterator + core_j + 1);
-
-        node->setSchTime(i);
-        isScheduled = true;
-        nodeScheduled.push_back(node);
-
-        break;
-      } else if (coreSchedule[core_i][core_j]) {
-        if (ModuloScheduling::printScheduleProcess())
-          DEBUG_PRINT(std::cerr << " Slot not available\n");
-      } else {
-        if (ModuloScheduling::printScheduleProcess())
-          DEBUG_PRINT(std::cerr << " Resource conflicts\n");
-      }
-    }
-    if (isScheduled)
-      break;
-  }
-  //assert(nodeScheduled &&"this node can not be scheduled?");
-  return isScheduled;
-}
-
-
-void 
-ModuloScheduling::updateResourceTable(Resources useResources,
-                                           int startCycle){
-
-  for (unsigned i = 0; i < useResources.size(); i++) {
-    int absCycle = startCycle + i;
-    int coreCycle = absCycle % II;
-    std::vector<std::pair<int,int> > &resourceRemained =
-        resourceTable[coreCycle];
-    std::vector < unsigned int >&resourceUsed = useResources[i];
-    for (unsigned j = 0; j < resourceUsed.size(); j++) {
-      for (unsigned k = 0; k < resourceRemained.size(); k++)
-        if ((int) resourceUsed[j] == resourceRemained[k].first) {
-          resourceRemained[k].second--;
-        }
-    }
-  }
-}
-
-void 
-ModuloScheduling::undoUpdateResourceTable(Resources useResources,
-                                               int startCycle){
-
-  for (unsigned i = 0; i < useResources.size(); i++) {
-    int absCycle = startCycle + i;
-    int coreCycle = absCycle % II;
-    std::vector<std::pair<int,int> > &resourceRemained =
-        resourceTable[coreCycle];
-    std::vector < unsigned int >&resourceUsed = useResources[i];
-    for (unsigned j = 0; j < resourceUsed.size(); j++) {
-      for (unsigned k = 0; k < resourceRemained.size(); k++)
-        if ((int) resourceUsed[j] == resourceRemained[k].first) {
-          resourceRemained[k].second++;
-        }
-    }
-  }
-}
-
-
-//-----------------------------------------------------------------------
-// Function: resourceTableNegative
-// return value:
-//   return false if any element in the resouceTable is negative
-//   otherwise return true
-// Purpose:
-
-//   this function is used to determine if an instruction is eligible for
-//   schedule at certain cycle
-//-----------------------------------------------------------------------
-
-
-bool 
-ModuloScheduling::resourceTableNegative(){
-
-  assert(resourceTable.size() == (unsigned) II
-         && "resouceTable size must be equal to II");
-  bool isNegative = false;
-  for (unsigned i = 0; i < resourceTable.size(); i++)
-    for (unsigned j = 0; j < resourceTable[i].size(); j++) {
-      if (resourceTable[i][j].second < 0) {
-        isNegative = true;
-        break;
-      }
-    }
-  return isNegative;
-}
-
-
-//----------------------------------------------------------------------
-// Function: dumpResouceUsageTable
-// Purpose:
-//   print out ResouceTable for debug
-//
-//------------------------------------------------------------------------
-
-void 
-ModuloScheduling::dumpResourceUsageTable(){
-
-  DEBUG_PRINT(std::cerr << "dumping resource usage table\n");
-  for (unsigned i = 0; i < resourceTable.size(); i++) {
-    for (unsigned j = 0; j < resourceTable[i].size(); j++)
-      DEBUG_PRINT(std::cerr << resourceTable[i][j].first 
-            << ":" << resourceTable[i][j].second << " ");
-    DEBUG_PRINT(std::cerr << "\n");
-  }
-
-}
-
-//----------------------------------------------------------------------
-//Function: dumpSchedule
-//Purpose:
-//       print out thisSchedule for debug
-//
-//-----------------------------------------------------------------------
-void 
-ModuloScheduling::dumpSchedule(vvNodeType thisSchedule){
-
-  const TargetSchedInfo & msi = target.getSchedInfo();
-  unsigned numIssueSlots = msi.maxNumIssueTotal;
-  for (unsigned i = 0; i < numIssueSlots; i++)
-    DEBUG_PRINT(std::cerr << "\t#");
-  DEBUG_PRINT(std::cerr << "\n");
-  for (unsigned i = 0; i < thisSchedule.size(); i++) {
-    DEBUG_PRINT(std::cerr << "cycle" << i << ": ");
-    for (unsigned j = 0; j < thisSchedule[i].size(); j++)
-      if (thisSchedule[i][j] != NULL)
-        DEBUG_PRINT(std::cerr << thisSchedule[i][j]->getNodeId() << "\t");
-      else
-        DEBUG_PRINT(std::cerr << "\t");
-    DEBUG_PRINT(std::cerr << "\n");
-  }
-}
-
-
-//----------------------------------------------------
-//Function: dumpScheduling
-//Purpose:
-//   print out the schedule and coreSchedule for debug      
-//
-//-------------------------------------------------------
-
-void 
-ModuloScheduling::dumpScheduling(){
-
-  DEBUG_PRINT(std::cerr << "dump schedule:" << "\n");
-  const TargetSchedInfo & msi = target.getSchedInfo();
-  unsigned numIssueSlots = msi.maxNumIssueTotal;
-  for (unsigned i = 0; i < numIssueSlots; i++)
-    DEBUG_PRINT(std::cerr << "\t#");
-  DEBUG_PRINT(std::cerr << "\n");
-  for (unsigned i = 0; i < schedule.size(); i++) {
-    DEBUG_PRINT(std::cerr << "cycle" << i << ": ");
-    for (unsigned j = 0; j < schedule[i].size(); j++)
-      if (schedule[i][j] != NULL)
-        DEBUG_PRINT(std::cerr << schedule[i][j]->getNodeId() << "\t");
-      else
-        DEBUG_PRINT(std::cerr << "\t");
-    DEBUG_PRINT(std::cerr << "\n");
-  }
-
-  DEBUG_PRINT(std::cerr << "dump coreSchedule:" << "\n");
-  for (unsigned i = 0; i < numIssueSlots; i++)
-    DEBUG_PRINT(std::cerr << "\t#");
-  DEBUG_PRINT(std::cerr << "\n");
-  for (unsigned i = 0; i < coreSchedule.size(); i++) {
-    DEBUG_PRINT(std::cerr << "cycle" << i << ": ");
-    for (unsigned j = 0; j < coreSchedule[i].size(); j++)
-      if (coreSchedule[i][j] != NULL)
-        DEBUG_PRINT(std::cerr << coreSchedule[i][j]->getNodeId() << "\t");
-      else
-        DEBUG_PRINT(std::cerr << "\t");
-    DEBUG_PRINT(std::cerr << "\n");
-  }
-}
-
-/*
-  print out final schedule
-*/
-
-void 
-ModuloScheduling::dumpFinalSchedule(){
-
-  std::cerr << "dump schedule:" << "\n";
-  const TargetSchedInfo & msi = target.getSchedInfo();
-  unsigned numIssueSlots = msi.maxNumIssueTotal;
-
-  for (unsigned i = 0; i < numIssueSlots; i++)
-    std::cerr << "\t#";
-  std::cerr << "\n";
-
-  for (unsigned i = 0; i < schedule.size(); i++) {
-    std::cerr << "cycle" << i << ": ";
+  class ModuloScheduling : public FunctionPass {
     
-    for (unsigned j = 0; j < schedule[i].size(); j++)
-      if (schedule[i][j] != NULL)
-        std::cerr << schedule[i][j]->getNodeId() << "\t";
-      else
-        std::cerr << "\t";
-    std::cerr << "\n";
-  }
-  
-  std::cerr << "dump coreSchedule:" << "\n";
-  for (unsigned i = 0; i < numIssueSlots; i++)
-    std::cerr << "\t#";
-  std::cerr << "\n";
-  
-  for (unsigned i = 0; i < coreSchedule.size(); i++) {
-    std::cerr << "cycle" << i << ": ";
-    for (unsigned j = 0; j < coreSchedule[i].size(); j++)
-      if (coreSchedule[i][j] != NULL)
-        std::cerr << coreSchedule[i][j]->getNodeId() << "\t";
-      else
-        std::cerr << "\t";
-    std::cerr << "\n";
-  }
-}
-
-//---------------------------------------------------------------------------
-// Function: ModuloSchedulingPass
-// 
-// Purpose:
-//   Entry point for Modulo Scheduling
-//   Schedules LLVM instruction
-//   
-//---------------------------------------------------------------------------
-
-namespace {
-  class ModuloSchedulingPass:public FunctionPass {
-    const TargetMachine &target;
-
   public:
-    ModuloSchedulingPass(const TargetMachine &T):target(T) {}
-
-    const char *getPassName() const {
-      return "Modulo Scheduling";
-    }
-
-    // getAnalysisUsage - We use LiveVarInfo...
-    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-      //AU.addRequired(FunctionLiveVarInfo::ID);
-    }
-    
-    bool runOnFunction(Function & F);
+    virtual bool runOnFunction(Function &F);
   };
-}                               // end anonymous namespace
 
+  RegisterOpt<ModuloScheduling> X("modulo-sched", "Modulo Scheduling/Software Pipelining");
+}
 
-bool
-ModuloSchedulingPass::runOnFunction(Function &F){
-  
-  ModuloSchedGraphSet *graphSet = new ModuloSchedGraphSet(&F, target);
-
-  ModuloSchedulingSet ModuloSchedulingSet(*graphSet);
-  
-  DEBUG_PRINT(std::cerr<<"runOnFunction  in ModuloSchedulingPass returns\n"<<"\n");
-  return false;
+//Create Modulo Scheduling Pass
+Pass *createModuloSchedPass() {
+  return new ModuloScheduling(); 
 }
 
+//ModuloScheduling::runOnFunction - Main transformation entry point.
+bool ModuloScheduling::runOnFunction(Function &F) {
+  bool Changed = false;
 
-Pass *
-createModuloSchedulingPass(const TargetMachine & tgt){
-  DEBUG_PRINT(std::cerr<<"creating modulo scheduling\n");
-  return new ModuloSchedulingPass(tgt);
+  return Changed;
 }
+
diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h
deleted file mode 100644
index 00cca149da..0000000000
--- a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h
+++ /dev/null
@@ -1,194 +0,0 @@
-// ModuloScheduling.h -------------------------------------------*- C++ -*-===//
-//
-// This header defines the the classes ModuloScheduling and 
-// ModuloSchedulingSet's structure
-//
-//===----------------------------------------------------------------------===//
-
-
-#ifndef LLVM_CODEGEN_MODULOSCHEDULING_H
-#define LLVM_CODEGEN_MODULOSCHEDULING_H
-
-#include "ModuloSchedGraph.h"
-#include <iostream>
-#include <vector>
-
-//#define DEBUG_PRINT(x) x
-
-#define DEBUG_PRINT(x) 
-
-// for debug information selecton
-enum ModuloSchedDebugLevel_t { 
-  ModuloSchedDebugLevel_NoDebugInfo,
-  ModuloSchedDebugLevel_PrintSchedule,
-  ModuloSchedDebugLevel_PrintScheduleProcess,
-};
-
-class ModuloScheduling: NonCopyable {
-private:
-
-  typedef std::vector<ModuloSchedGraphNode*> NodeVec;
-  typedef std::vector<std::vector<unsigned> > Resources;
-
-  // The graph to feed in
-  ModuloSchedGraph &graph;
-  const TargetMachine &target;
-
-  // The BasicBlock to be scheduled
-  BasicBlock *bb;
-
-  // Iteration Interval
-  // FIXME: II may be a better name for its meaning
-  unsigned II;
-
-  // The vector containing the nodes which have been scheduled
-  NodeVec nodeScheduled;
-
-  // The remaining unscheduled nodes 
-  const NodeVec &oNodes;
-
-  // The machine resource table
-  std::vector<std::vector<std::pair<int,int> > > resourceTable;
-
-  ///the schedule( with many schedule stage)
-  std::vector<std::vector<ModuloSchedGraphNode*> > schedule;
-
-  ///the kernel(core) schedule(length = II)
-  std::vector<std::vector<ModuloSchedGraphNode*> > coreSchedule;
-
-  typedef BasicBlock::InstListType InstListType;
-  typedef std::vector<std::vector<ModuloSchedGraphNode*> > vvNodeType;
-
-
-
-
-
-public:
-
-  ModuloScheduling(ModuloSchedGraph & _graph):
-    graph(_graph), target(graph.getTarget()), oNodes(graph.getONodes())
-  {
-    II = graph.getMII();
-    bb = graph.getBasicBlock();
-    instrScheduling();
-  };
-
-  ~ModuloScheduling() {};
-
-
-
-  static bool 
-  printSchedule() { 
-
-    //return ModuloScheduling::DebugLevel >= DebugLevel_PrintSchedule; 
-    return true;
-
-    
-  }
-  static bool 
-  printScheduleProcess() {
-  
-    //return DebugLevel >= DebugLevel_PrintScheduleProcess;
-    return true;
-
-
-  }
-
-  // The method to compute schedule and instert epilogue and prologue
-  void instrScheduling();
-
-  // Debug functions:
-  // Dump the schedule and core schedule
-  void dumpScheduling();
-  void dumpFinalSchedule();
-
-  // Dump the input vector of nodes
-  // sch: the input vector of nodes
-  void dumpSchedule(std::vector<std::vector<ModuloSchedGraphNode*> > sch);
-
-  // Dump the resource usage table
-  void dumpResourceUsageTable();
-
-  //*******************internal functions*******************************
-private:
-  //clear memory from the last round and initialize if necessary
-  void clearInitMem(const TargetSchedInfo&);
-
-  //compute schedule and coreSchedule with the current II
-  bool computeSchedule();
-
-  BasicBlock *getSuccBB(BasicBlock *);
-  BasicBlock *getPredBB(BasicBlock *);
-  void constructPrologue(BasicBlock *prologue);
-  void constructKernel(BasicBlock *prologue,
-                       BasicBlock *kernel,
-                       BasicBlock *epilogue);
-  void constructEpilogue(BasicBlock *epilogue, BasicBlock *succ_bb);
-
-  // update the resource table at the startCycle
-  // vec: the resouce usage
-  // startCycle: the start cycle the resouce usage is
-  void updateResourceTable(std::vector<std::vector<unsigned> > vec,
-                           int startCycle);
-
-  // un-do the update in the resource table in the startCycle
-  // vec: the resouce usage
-  // startCycle: the start cycle the resouce usage is
-  void undoUpdateResourceTable(std::vector<std::vector<unsigned> > vec,
-                               int startCycle);
-
-  // return whether the resourcetable has negative element
-  // this function is called after updateResouceTable() to determine whether a
-  // node can be scheduled at certain cycle
-  bool resourceTableNegative();
-
-  // try to Schedule the node starting from start to end cycle(inclusive)
-  // if it can be scheduled, put it in the schedule and update nodeScheduled
-  // node: the node to be scheduled
-  // start: start cycle
-  // end : end cycle
-  // nodeScheduled: a vector storing nodes which has been scheduled
-  bool ScheduleNode(ModuloSchedGraphNode * node, unsigned start,
-                    unsigned end, NodeVec &nodeScheduled);
-
-  //each instruction has a memory of the latest clone instruction
-  //the clone instruction can be get using getClone() 
-  //this function clears the memory, i.e. getClone() after calling this function
-  //returns null
-  void clearCloneMemory();
-
-  //this fuction make a clone of this input Instruction and update the clone
-  //memory
-  //inst: the instrution to be cloned
-  Instruction *cloneInstSetMemory(Instruction *inst);
-
-  //this function update each instrutions which uses ist as its operand
-  //after update, each instruction will use ist's clone as its operand
-  void updateUseWithClone(Instruction * ist);
-
-};
-
-
-class ModuloSchedulingSet:
-NonCopyable {
-private:
-
-  //the graphSet to feed in
-  ModuloSchedGraphSet & graphSet;
-
-public:
-
-  //constructor
-  //Scheduling graph one by one
-  ModuloSchedulingSet(ModuloSchedGraphSet _graphSet): graphSet(_graphSet) {
-    for (unsigned i = 0; i < graphSet.size(); i++) {
-      ModuloSchedGraph & graph = *(graphSet[i]);
-      if (graph.isLoop(graph.getBasicBlock()))
-        ModuloScheduling ModuloScheduling(graph);
-    }
-  };
-
-  ~ModuloSchedulingSet() {};
-};
-
-#endif