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

4 files changed, 155 insertions, 2940 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)
-{
-  
-  as