Numerous bug fixes and the completed modschedSB algorithm (minor bugs still exist for course).

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

7 files changed, 3304 insertions, 194 deletions

diff --git a/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp b/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp
index 25ad03ad7d..d0b5db304a 100644
--- a/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp
+++ b/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp
@@ -159,10 +159,10 @@ void DependenceAnalyzer::advancedDepAnalysis(GetElementPtrInst *gp1,
   SCEVHandle SV2 = SE->getSCEV(Gep2Idx);
 
   //Now handle special cases of dependence analysis
-  SV1->print(std::cerr);
-  std::cerr << "\n";
-  SV2->print(std::cerr);
-  std::cerr << "\n";
+  //SV1->print(std::cerr);
+  //std::cerr << "\n";
+  //SV2->print(std::cerr);
+  //std::cerr << "\n";
 
   //Check if we have an SCEVAddExpr, cause we can only handle those
   SCEVAddRecExpr *SVAdd1 = dyn_cast<SCEVAddRecExpr>(SV1);
@@ -217,7 +217,7 @@ void DependenceAnalyzer::advancedDepAnalysis(GetElementPtrInst *gp1,
   
   //Find constant index difference
   int diff = A1->getValue()->getRawValue() - A2->getValue()->getRawValue();
-  std::cerr << diff << "\n";
+  //std::cerr << diff << "\n";
   if(diff > 5)
     diff = 2;
 
@@ -240,14 +240,21 @@ void DependenceAnalyzer::createDep(std::vector<Dependence> &deps,
 
   //If load/store pair
   if(valLoad && !val2Load) {
-    //Anti Dep
-    deps.push_back(Dependence(diff, Dependence::AntiDep));
+    if(srcBeforeDest) 
+      //Anti Dep
+      deps.push_back(Dependence(diff, Dependence::AntiDep));
+    else
+      deps.push_back(Dependence(diff, Dependence::TrueDep));
+
     ++NumDeps;
   }
   //If store/load pair
   else if(!valLoad && val2Load) {
-    //True Dep
-    deps.push_back(Dependence(diff, Dependence::TrueDep));
+    if(srcBeforeDest) 
+      //True Dep
+      deps.push_back(Dependence(diff, Dependence::TrueDep));
+    else
+      deps.push_back(Dependence(diff, Dependence::AntiDep));
     ++NumDeps;
   }
   //If store/store pair
diff --git a/lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp b/lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp
index d1aaa4f46b..6e8a6db347 100644
--- a/lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp
+++ b/lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp
@@ -16,18 +16,23 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/Target/TargetSchedInfo.h"
 #include "../SparcV9Internals.h"
+#include "llvm/CodeGen/MachineInstr.h"
 
 using namespace llvm;
 
+//Check if all resources are free
+bool resourcesFree(MSchedGraphNode*, int, 
+std::map<int, std::map<int, int> > &resourceNumPerCycle);
+
 //Returns a boolean indicating if the start cycle needs to be increased/decreased
-bool MSSchedule::insert(MSchedGraphNode *node, int cycle) {
+bool MSSchedule::insert(MSchedGraphNode *node, int cycle, int II) {
 
   //First, check if the cycle has a spot free to start
   if(schedule.find(cycle) != schedule.end()) {
     //Check if we have a free issue slot at this cycle
     if (schedule[cycle].size() < numIssue) {
       //Now check if all the resources in their respective cycles are available
-      if(resourcesFree(node, cycle)) {
+      if(resourcesFree(node, cycle, II)) {
 	//Insert to preserve dependencies
 	addToSchedule(cycle,node);
 	DEBUG(std::cerr << "Found spot in map, and there is an issue slot\n");
@@ -37,7 +42,7 @@ bool MSSchedule::insert(MSchedGraphNode *node, int cycle) {
   }
   //Not in the map yet so put it in
   else {
-    if(resourcesFree(node,cycle)) {
+    if(resourcesFree(node,cycle,II)) {
       std::vector<MSchedGraphNode*> nodes;
       nodes.push_back(node);
       schedule[cycle] = nodes;
@@ -68,99 +73,113 @@ void MSSchedule::addToSchedule(int cycle, MSchedGraphNode *node) {
   schedule[cycle] =  nodes;
 }
 
+bool MSSchedule::resourceAvailable(int resourceNum, int cycle) {
+  bool isFree = true;
+
+  //Get Map for this cycle
+  if(resourceNumPerCycle.count(cycle)) {
+    if(resourceNumPerCycle[cycle].count(resourceNum)) {
+      int maxRes = CPUResource::getCPUResource(resourceNum)->maxNumUsers;
+      if(resourceNumPerCycle[cycle][resourceNum] >= maxRes)
+	isFree = false;
+    }
+  }
+  
+  return isFree;
+}
+
+void MSSchedule::useResource(int resourceNum, int cycle) {
+  
+  //Get Map for this cycle
+  if(resourceNumPerCycle.count(cycle)) {
+    if(resourceNumPerCycle[cycle].count(resourceNum)) {
+      resourceNumPerCycle[cycle][resourceNum]++;
+    }
+    else {
+      resourceNumPerCycle[cycle][resourceNum] = 1;
+    }
+  }
+  //If no map, create one!
+  else {
+    std::map<int, int> resourceUse;
+    resourceUse[resourceNum] = 1;
+    resourceNumPerCycle[cycle] = resourceUse;
+  }
+  
+}
 
-bool MSSchedule::resourcesFree(MSchedGraphNode *node, int cycle) {
+bool MSSchedule::resourcesFree(MSchedGraphNode *node, int cycle, int II) {
 
   //Get Resource usage for this instruction
   const TargetSchedInfo *msi = node->getParent()->getTarget()->getSchedInfo();
   int currentCycle = cycle;
   bool success = true;
 
-  //Get resource usage for this instruction
-  InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode());
-  std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
+  //Create vector of starting cycles
+  std::vector<int> cyclesMayConflict;
+  cyclesMayConflict.push_back(cycle);
 
-  //Loop over resources in each cycle and increments their usage count
-  for(unsigned i=0; i < resources.size(); ++i) {
-    for(unsigned j=0; j < resources[i].size(); ++j) {
-
-      //Get Resource to check its availability
-      int resourceNum = resources[i][j];
-
-      DEBUG(std::cerr << "Attempting to schedule Resource Num: " << resourceNum << " in cycle: " << currentCycle << "\n");
-
-	//Check if this resource is available for this cycle
-	std::map<int, std::map<int,int> >::iterator resourcesForCycle = resourceNumPerCycle.find(currentCycle);
+  if(resourceNumPerCycle.size() > 0) {
+    for(int i = cycle-II; i >= (resourceNumPerCycle.begin()->first); i-=II)
+      cyclesMayConflict.push_back(i);
+    for(int i = cycle+II; i <= resourceNumPerCycle.end()->first; i+=II)
+      cyclesMayConflict.push_back(i);
+  }
 
-	//First check if map exists for this cycle
-	if(resourcesForCycle != resourceNumPerCycle.end()) {
-	  //A map exists for this cycle, so lets check for the resource
-	  std::map<int, int>::iterator resourceUse = resourcesForCycle->second.find(resourceNum);
-	  if(resourceUse != resourcesForCycle->second.end()) {
-	    //Check if there are enough of this resource and if so, increase count and move on
-	    if(resourceUse->second < CPUResource::getCPUResource(resourceNum)->maxNumUsers)
-	      ++resourceUse->second;
+  //Now check all cycles for conflicts
+  for(int index = 0; index < (int) cyclesMayConflict.size(); ++index) {
+    currentCycle = cyclesMayConflict[index];
+    
+    //Get resource usage for this instruction
+    InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode());
+    std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
+    
+    //Loop over resources in each cycle and increments their usage count
+    for(unsigned i=0; i < resources.size(); ++i) {
+      for(unsigned j=0; j < resources[i].size(); ++j) {
 	
-	    else {
-	      DEBUG(std::cerr << "No resource num " << resourceNum << " available for cycle " << currentCycle << "\n");
-	      success = false;
-	    }
-	  }
-	  //Not in the map yet, so put it
-	  else
-	    resourcesForCycle->second[resourceNum] = 1;
+	//Get Resource to check its availability
+	int resourceNum = resources[i][j];
+	
+	DEBUG(std::cerr << "Attempting to schedule Resource Num: " << resourceNum << " in cycle: " << currentCycle << "\n");
+	
+	success = resourceAvailable(resourceNum, currentCycle); 
 	
-	}
-	else {
-	  //Create a new map and put in our resource
-	  std::map<int, int> resourceMap;
-	  resourceMap[resourceNum] = 1;
-	  resourceNumPerCycle[currentCycle] = resourceMap;
-	}
 	if(!success)
 	  break;
+	
       }
+      
       if(!success)
 	break;
-	
-
+      
       //Increase cycle
       currentCycle++;
+    }
+    
+    if(!success)
+      return false;
   }
 
-  if(!success) {
-    int oldCycle = cycle;
-    DEBUG(std::cerr << "Backtrack\n");
+  //Actually put resources into the map
+  if(success) {
+
+    int currentCycle = cycle;
     //Get resource usage for this instruction
     InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode());
     std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
-
+    
     //Loop over resources in each cycle and increments their usage count
     for(unsigned i=0; i < resources.size(); ++i) {
-      if(oldCycle < currentCycle) {
-	
-	//Check if this resource is available for this cycle
-	std::map<int, std::map<int,int> >::iterator resourcesForCycle = resourceNumPerCycle.find(oldCycle);
-	if(resourcesForCycle != resourceNumPerCycle.end()) {
-	  for(unsigned j=0; j < resources[i].size(); ++j) {
-	    int resourceNum = resources[i][j];
-	    //remove from map
-	    std::map<int, int>::iterator resourceUse = resourcesForCycle->second.find(resourceNum);
-	    //assert if not in the map.. since it should be!
-	    //assert(resourceUse != resourcesForCycle.end() && "Resource should be in map!");
-	    DEBUG(std::cerr << "Removing resource num " << resourceNum << " from cycle " << oldCycle << "\n");
-	    --resourceUse->second;
-	  }
-	}
+      for(unsigned j=0; j < resources[i].size(); ++j) {
+	int resourceNum = resources[i][j];
+	useResource(resourceNum, currentCycle);
       }
-      else
-	break;
-      oldCycle++;
+      currentCycle++;
     }
-    return false;
-
   }
 
+
   return true;
 
 }
@@ -174,12 +193,9 @@ bool MSSchedule::constructKernel(int II, std::vector<MSchedGraphNode*> &branches
 
   DEBUG(std::cerr << "Offset: " << offset << "\n");
 
-  //Not sure what happens in this case, but assert if offset is > II
-  //assert(offset > -II && "Offset can not be more then II");
-
+  //Using the schedule, fold up into kernel and check resource conflicts as we go
   std::vector<std::pair<MSchedGraphNode*, int> > tempKernel;
-
-
+  
   int stageNum = ((schedule.rbegin()->first-offset)+1)/ II;
   int maxSN = 0;
 
@@ -192,21 +208,18 @@ bool MSSchedule::constructKernel(int II, std::vector<MSchedGraphNode*> &branches
 	for(std::vector<MSchedGraphNode*>::iterator I = schedule[i].begin(),
 	      E = schedule[i].end(); I != E; ++I) {
 	  //Check if its a branch
-	  if((*I)->isBranch()) {
-	    assert(count == 0 && "Branch can not be from a previous iteration");
-	    tempKernel.push_back(std::make_pair(*I, count));
-	  }
-	  else {
-	  //FIXME: Check if the instructions in the earlier stage conflict
-	    tempKernel.push_back(std::make_pair(*I, count));
-	    maxSN = std::max(maxSN, count);
-	  }
+	  assert(!(*I)->isBranch() && "Branch should not be schedule!");
+
+	  tempKernel.push_back(std::make_pair(*I, count));
+	  maxSN = std::max(maxSN, count);
+	  
 	}
       }
       ++count;
     }
   }
 
+
   //Add in induction var code
   for(std::vector<std::pair<MSchedGraphNode*, int> >::iterator I = tempKernel.begin(), IE = tempKernel.end();
       I != IE; ++I) {
@@ -253,6 +266,30 @@ bool MSSchedule::constructKernel(int II, std::vector<MSchedGraphNode*> &branches
   return true;
 }
 
+bool MSSchedule::defPreviousStage(Value *def, int stage) {
+
+  //Loop over kernel and determine if value is being defined in previous stage
+  for(std::vector<std::pair<MachineInstr*, int> >::iterator P = kernel.begin(), PE = kernel.end(); P != PE; ++P) {
+    MachineInstr* inst = P->first;
+
+    //Loop over Machine Operands
+    for(unsigned i=0; i < inst->getNumOperands(); ++i) {
+      //get machine operand
+     const MachineOperand &mOp = inst->getOperand(i);
+     if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) {
+       if(def == mOp.getVRegValue()) {
+	 if(P->second >= stage)
+	   return false;
+	 else
+	   return true;
+       }
+     }
+    }
+  }
+  
+  assert(0 && "We should always have found the def in our kernel\n");
+}
+
 
 void MSSchedule::print(std::ostream &os) const {
   os << "Schedule:\n";
diff --git a/lib/Target/SparcV9/ModuloScheduling/MSSchedule.h b/lib/Target/SparcV9/ModuloScheduling/MSSchedule.h
index d9f42a25b4..92a942b43c 100644
--- a/lib/Target/SparcV9/ModuloScheduling/MSSchedule.h
+++ b/lib/Target/SparcV9/ModuloScheduling/MSSchedule.h
@@ -28,7 +28,9 @@ namespace llvm {
     std::map<int, std::map<int, int> > resourceNumPerCycle;
 
     //Check if all resources are free
-    bool resourcesFree(MSchedGraphNode*, int);
+    bool resourcesFree(MSchedGraphNode*, int, int II); 
+    bool resourceAvailable(int resourceNum, int cycle);
+    void useResource(int resourceNum, int cycle);
 
     //Resulting kernel
     std::vector<std::pair<MachineInstr*, int> > kernel;
@@ -42,13 +44,13 @@ namespace llvm {
   public:
     MSSchedule(int num) : numIssue(num) {}
     MSSchedule() : numIssue(4) {}
-    bool insert(MSchedGraphNode *node, int cycle);
+    bool insert(MSchedGraphNode *node, int cycle, int II);
     int getStartCycle(MSchedGraphNode *node);
     void clear() { schedule.clear(); resourceNumPerCycle.clear(); kernel.clear(); }
     std::vector<std::pair<MachineInstr*, int> >* getKernel() { return &kernel; }
     bool constructKernel(int II, std::vector<MSchedGraphNode*> &branches, std::map<const MachineInstr*, unsigned> &indVar);
     int getMaxStage() { return maxStage; }
-
+    bool defPreviousStage(Value *def, int stage);
 
     //iterators
     typedef std::map<int, std::vector<MSchedGraphNode*> >::iterator schedule_iterator;
diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp
index 4e57c65aae..65008a67f8 100644
--- a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp
+++ b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp
@@ -178,7 +178,7 @@ bool ModuloSchedulingPass::runOnFunction(Function &F) {
       }
       else
 	++JumboBB;
-      std::cerr << "BB Size: " << BI->size() << "\n";
+      
     }
 
   defaultInst = 0;
@@ -230,7 +230,6 @@ bool ModuloSchedulingPass::runOnFunction(Function &F) {
 
     II = std::max(RecMII, ResMII);
     int mII = II;
-    IISum += mII;
 
     //Print out II, RecMII, and ResMII
     DEBUG(std::cerr << "II starts out as " << II << " ( RecMII=" << RecMII << " and ResMII=" << ResMII << ")\n");
@@ -285,12 +284,15 @@ bool ModuloSchedulingPass::runOnFunction(Function &F) {
       reconstructLoop(*BI);
       ++MSLoops;
       Changed = true;
+      FinalIISum += II;
+      IISum += mII;
 
       if(schedule.getMaxStage() == 0)
 	++SameStage;
     }
-    else
+    else {
       ++NoSched;
+    }
 
     //Clear out our maps for the next basic block that is processed
     nodeToAttributesMap.clear();
@@ -323,7 +325,9 @@ bool ModuloSchedulingPass::CreateDefMap(MachineBasicBlock *BI) {
       if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) {
 	//assert if this is the second def we have seen
 	//DEBUG(std::cerr << "Putting " << *(mOp.getVRegValue()) << " into map\n");
-	assert(!defMap.count(mOp.getVRegValue()) && "Def already in the map");
+	//assert(!defMap.count(mOp.getVRegValue()) && "Def already in the map");
+	if(defMap.count(mOp.getVRegValue()))
+	  return false;
 
 	defMap[mOp.getVRegValue()] = &*I;
       }
@@ -397,7 +401,7 @@ bool ModuloSchedulingPass::MachineBBisValid(const MachineBasicBlock *BI) {
        || OC == V9::MOVRGEZi || OC == V9::MOVLEr || OC == V9::MOVLEi || OC == V9::MOVLEUr
        || OC == V9::MOVLEUi || OC == V9::MOVFLEr || OC == V9::MOVFLEi
        || OC == V9::MOVNEr || OC == V9::MOVNEi || OC == V9::MOVNEGr || OC == V9::MOVNEGi
-       || OC == V9::MOVFNEr || OC == V9::MOVFNEi) {
+       || OC == V9::MOVFNEr || OC == V9::MOVFNEi || OC == V9::MOVGr || OC == V9::MOVGi) {
       ++LoopsWithCondMov;
       return false;
     }
@@ -579,6 +583,8 @@ int ModuloSchedulingPass::calculateResMII(const MachineBasicBlock *BI) {
     //Divide the usage count by either the max number we can issue or the number of
     //resources (whichever is its upper bound)
     double finalUsageCount;
+    DEBUG(std::cerr << "Resource Num: " << RB->first << " Usage: " << usageCount << " TotalNum: " << resourceNum << "\n");
+
     if( resourceNum <= issueSlots)
       finalUsageCount = ceil(1.0 * usageCount / resourceNum);
     else
@@ -1035,6 +1041,56 @@ void ModuloSchedulingPass::addRecc(std::vector<MSchedGraphNode*> &stack, std::ma
 
 }
 
+void ModuloSchedulingPass::addSCC(std::vector<MSchedGraphNode*> &SCC, std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes) {
+
+  int totalDelay = 0;
+  int totalDistance = 0;
+  std::vector<MSchedGraphNode*> recc;
+  MSchedGraphNode *start = 0;
+  MSchedGraphNode *end = 0;
+
+  //Loop over recurrence, get delay and distance
+  for(std::vector<MSchedGraphNode*>::iterator N = SCC.begin(), NE = SCC.end(); N != NE; ++N) {
+    DEBUG(std::cerr << **N << "\n");
+    totalDelay += (*N)->getLatency();
+    
+    for(unsigned i = 0; i < (*N)->succ_size(); ++i) {
+      MSchedGraphEdge *edge = (*N)->getSuccessor(i);
+      if(find(SCC.begin(), SCC.end(), edge->getDest()) != SCC.end()) {
+	totalDistance += edge->getIteDiff();
+	if(edge->getIteDiff() > 0)
+	  if(!start && !end) {
+	    start = *N;
+	    end = edge->getDest();
+	  }
+	    
+      }
+    }
+
+
+    //Get the original node
+    recc.push_back(newNodes[*N]);
+
+
+  }
+
+  DEBUG(std::cerr << "End Recc\n");
+  CircCount++;
+
+  assert( (start && end) && "Must have start and end node to ignore edge for SCC");
+
+  if(start && end) {	
+    //Insert reccurrence into the list
+    DEBUG(std::cerr << "Ignore Edge from!!: " << *start << " to " << *end << "\n");
+    edgesToIgnore.insert(std::make_pair(newNodes[start], (newNodes[end])->getInEdgeNum(newNodes[start])));
+  }
+
+  int lastII = totalDelay / totalDistance;
+
+
+  recurrenceList.insert(std::make_pair(lastII, recc));
+
+}
 
 void ModuloSchedulingPass::findAllCircuits(MSchedGraph *g, int II) {
 
@@ -1074,6 +1130,7 @@ void ModuloSchedulingPass::findAllCircuits(MSchedGraph *g, int II) {
     std::set<MSchedGraphNode*> Visited;
     std::vector<MSchedGraphNode*> Vk;
     MSchedGraphNode* s = 0;
+    int numEdges = 0;
 
     //Find scc with the least vertex
     for (MSchedGraph::iterator GI = MSG->begin(), E = MSG->end(); GI != E; ++GI)
@@ -1085,7 +1142,19 @@ void ModuloSchedulingPass::findAllCircuits(MSchedGraph *g, int II) {
 	  if (Visited.insert(nextSCC[0]).second) {
 	    Visited.insert(nextSCC.begin()+1, nextSCC.end());
 
-	    DEBUG(std::cerr << "SCC size: " << nextSCC.size() << "\n");
+	    if(nextSCC.size() > 1) {
+	      std::cerr << "SCC size: " << nextSCC.size() << "\n";
+	      
+	      for(unsigned i = 0; i < nextSCC.size(); ++i) {
+		//Loop over successor and see if in scc, then count edge
+		MSchedGraphNode *node = nextSCC[i];
+		for(MSchedGraphNode::succ_iterator S = node->succ_begin(), SE = node->succ_end(); S != SE; ++S) {
+		  if(find(nextSCC.begin(), nextSCC.end(), *S) != nextSCC.end())
+		    numEdges++;
+		}
+	      }
+	      std::cerr << "Num Edges: " << numEdges << "\n";
+	    }
 
 	    //Ignore self loops
 	    if(nextSCC.size() > 1) {
@@ -1120,7 +1189,10 @@ void ModuloSchedulingPass::findAllCircuits(MSchedGraph *g, int II) {
       B[*N].clear();
     }
     if(Vk.size() > 1) {
-      circuit(s, stack, blocked, Vk, s, B, II, newNodes);
+      if(numEdges < 98)
+	circuit(s, stack, blocked, Vk, s, B, II, newNodes);
+      else
+	addSCC(Vk, newNodes);
 
       //Delete nodes from the graph
       //Find all nodes up to s and delete them
@@ -1860,8 +1932,8 @@ bool ModuloSchedulingPass::computeSchedule(const MachineBasicBlock *BB, MSchedGr
 	schedule.clear();
       }
       DEBUG(std::cerr << "Final II: " << II << "\n");
-      FinalIISum += II;
     }
+   
 
     if(II >= capII) {
       DEBUG(std::cerr << "Maximum II reached, giving up\n");
@@ -1900,7 +1972,7 @@ bool ModuloSchedulingPass::scheduleNode(MSchedGraphNode *node,
 
     increaseSC = false;
 
-    increaseSC = schedule.insert(node, cycle);
+    increaseSC = schedule.insert(node, cycle, II);
 
     if(!increaseSC)
       return true;
@@ -2034,18 +2106,11 @@ void ModuloSchedulingPass::writePrologues(std::vector<MachineBasicBlock *> &prol
       }
     }
 
-
-    /*for(std::vector<MSchedGraphNode*>::iterator BR = branches.begin(), BE = branches.end(); BR != BE; ++BR) {
-
-      //Stick in branch at the end
-      machineBB->push_back((*BR)->getInst()->clone());
-
-      //Add nop
-      BuildMI(machineBB, V9::NOP, 0);
-      }*/
-
-
-  (((MachineBasicBlock*)origBB)->getParent())->getBasicBlockList().push_back(machineBB);
+    MachineFunction *F = (((MachineBasicBlock*)origBB)->getParent());
+    MachineFunction::BasicBlockListType &BL = F->getBasicBlockList();
+    MachineFunction::BasicBlockListType::iterator BLI = origBB;
+    assert(BLI != BL.end() && "Must find original BB in machine function\n");
+    BL.insert(BLI,machineBB);
     prologues.push_back(machineBB);
     llvm_prologues.push_back(llvmBB);
   }
@@ -2143,12 +2208,16 @@ void ModuloSchedulingPass::writeEpilogues(std::vector<MachineBasicBlock *> &epil
       }
      }
 
-    (((MachineBasicBlock*)origBB)->getParent())->getBasicBlockList().push_back(machineBB);
-    epilogues.push_back(machineBB);
-    llvm_epilogues.push_back(llvmBB);
-
-    DEBUG(std::cerr << "EPILOGUE #" << i << "\n");
-    DEBUG(machineBB->print(std::cerr));
+     MachineFunction *F = (((MachineBasicBlock*)origBB)->getParent());
+     MachineFunction::BasicBlockListType &BL = F->getBasicBlockList();
+     MachineFunction::BasicBlockListType::iterator BLI = (MachineBasicBlock*) origBB;
+     assert(BLI != BL.end() && "Must find original BB in machine function\n");
+     BL.insert(BLI,machineBB);
+     epilogues.push_back(machineBB);
+     llvm_epilogues.push_back(llvmBB);
+     
+     DEBUG(std::cerr << "EPILOGUE #" << i << "\n");
+     DEBUG(machineBB->print(std::cerr));
   }
 }
 
@@ -2170,14 +2239,6 @@ void ModuloSchedulingPass::writeKernel(BasicBlock *llvmBB, MachineBasicBlock *ma
 
    DEBUG(std::cerr << "Stage: " << I->second << " Inst: " << *(I->first) << "\n";);
 
-   /*if(I->first->isBranch()) {
-     //Clone instruction
-     const MachineInstr *inst = I->first->getInst();
-     MachineInstr *instClone = inst->clone();
-     branches.push_back(instClone);
-     continue;
-     }*/
-
    //Clone instruction
    const MachineInstr *inst = I->first;
    MachineInstr *instClone = inst->clone();
@@ -2208,6 +2269,8 @@ void ModuloSchedulingPass::writeKernel(BasicBlock *llvmBB, MachineBasicBlock *ma
 
 	   //Check if we already have a final PHI value for this
 	   if(!finalPHIValue.count(mOp.getVRegValue())) {
+	     //Only create phi if the operand def is from a stage before this one
+	     if(schedule.defPreviousStage(mOp.getVRegValue(), I->second)) {
 	     TmpInstruction *tmp = new TmpInstruction(mOp.getVRegValue());
 	
 	     //Get machine code for this instruction
@@ -2220,6 +2283,7 @@ void ModuloSchedulingPass::writeKernel(BasicBlock *llvmBB, MachineBasicBlock *ma
 	     //save this as our final phi
 	     finalPHIValue[mOp.getVRegValue()] = tmp;
 	     newValLocation[tmp] = machineBB;
+	     }
 	   }
 	   else {
 	     //Use the previous final phi value
@@ -2538,6 +2602,7 @@ void ModuloSchedulingPass::reconstructLoop(MachineBasicBlock *BB) {
   //Keep track of instructions we have already seen and their stage because
   //we don't want to "save" values if they are used in the kernel immediately
   std::map<const MachineInstr*, int> lastInstrs;
+  std::map<const Value*, int> phiUses;
 
   //Loop over kernel and only look at instructions from a stage > 0
   //Look at its operands and save values *'s that are read
@@ -2557,7 +2622,7 @@ void ModuloSchedulingPass::reconstructLoop(MachineBasicBlock *BB) {
 	  //find the value in the map
 	  if (const Value* srcI = mOp.getVRegValue()) {
 
-	    if(isa<Constant>(srcI) || isa<Argument>(srcI) || isa<PHINode>(srcI))
+	    if(isa<Constant>(srcI) || isa<Argument>(srcI))
 	      continue;
 
 	    //Before we declare this Value* one that we should save
@@ -2582,9 +2647,27 @@ void ModuloSchedulingPass::reconstructLoop(MachineBasicBlock *BB) {
 	      }
 	    }
 	
-	    if(save)
+	    if(save) {
+	      assert(!phiUses.count(srcI) && "Did not expect to see phi use twice");
+	      if(isa<PHINode>(srcI))
+		phiUses[srcI] = I->second;
+	      
 	      valuesToSave[srcI] = std::make_pair(I->first, i);
-	  }	
+
+	    }
+	  }
+	}
+	else if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) {
+	  if (const Value* destI = mOp.getVRegValue()) {
+	    if(!isa<PHINode>(destI))
+	      continue;
+	    if(phiUses.count(destI)) {
+	      if(phiUses[destI] == I->second) {
+		//remove from save list
+		valuesToSave.erase(destI);
+	      }
+	    }
+	  }
 	}
 	
 	if(mOp.getType() != MachineOperand::MO_VirtualRegister && mOp.isUse()) {
@@ -2623,7 +2706,14 @@ void ModuloSchedulingPass::reconstructLoop(MachineBasicBlock *BB) {
 
   BasicBlock *llvmKernelBB = new BasicBlock("Kernel", (Function*) (BB->getBasicBlock()->getParent()));
   MachineBasicBlock *machineKernelBB = new MachineBasicBlock(llvmKernelBB);
-  (((MachineBasicBlock*)BB)->getParent())->getBasicBlockList().push_back(machineKernelBB);
+ 
+  MachineFunction *F = (((MachineBasicBlock*)BB)->getParent());
+  MachineFunction::BasicBlockListType &BL = F->getBasicBlockList();
+  MachineFunction::BasicBlockListType::iterator BLI = BB;
+  assert(BLI != BL.end() && "Must find original BB in machine function\n");
+  BL.insert(BLI,machineKernelBB);
+
+  //(((MachineBasicBlock*)BB)->getParent())->getBasicBlockList().push_back(machineKernelBB);
   writeKernel(llvmKernelBB, machineKernelBB, valuesToSave, newValues, newValLocation, kernelPHIs);
 
 
@@ -2833,7 +2923,8 @@ void ModuloSchedulingPass::fixBranches(std::vector<MachineBasicBlock *> &prologu
 		 for(unsigned opNum = 0; opNum < temp->getNumOperands(); ++opNum) {
 		   MachineOperand &mOp = temp->getOperand(opNum);
 		   if (mOp.getType() == MachineOperand::MO_PCRelativeDisp) {
-		     mOp.setValueReg(llvm_prologues[0]);
+		     if(mOp.getVRegValue() == llvmBB)
+		       mOp.setValueReg(llvm_prologues[0]);
 		   }
 		 }
 	       }
@@ -2853,7 +2944,8 @@ void ModuloSchedulingPass::fixBranches(std::vector<MachineBasicBlock *> &prologu
 		 for(unsigned opNum = 0; opNum < temp->getNumOperands(); ++opNum) {
 		   MachineOperand &mOp = temp->getOperand(opNum);
 		   if (mOp.getType() == MachineOperand::MO_PCRelativeDisp) {
-		     mOp.setValueReg(llvmKernelBB);
+		     if(mOp.getVRegValue() == llvmBB)
+		       mOp.setValueReg(llvmKernelBB);
 		   }
 		 }
 	       }
diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h
index 263a6130de..f47de9f357 100644
--- a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h
+++ b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h
@@ -98,6 +98,7 @@ namespace llvm {
     void findAllReccurrences(MSchedGraphNode *node,
 			     std::vector<MSchedGraphNode*> &visitedNodes, int II);
     void addReccurrence(std::vector<MSchedGraphNode*> &recurrence, int II, MSchedGraphNode*, MSchedGraphNode*);
+    void addSCC(std::vector<MSchedGraphNode*> &SCC, std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes);
 
     void findAllCircuits(MSchedGraph *MSG, int II);
     bool circuit(MSchedGraphNode *v, std::vector<MSchedGraphNode*> &stack,
@@ -142,7 +143,7 @@ namespace llvm {
 
     void writeKernel(BasicBlock *llvmBB, MachineBasicBlock *machineBB, std::map<const Value*, std::pair<const MachineInstr*, int> > &valuesToSave, std::map<Value*, std::map<int, Value*> > &newValues, std::map<Value*, MachineBasicBlock*> &newValLocation, std::map<Value*, std::map<int, Value*> > &kernelPHIs);
 
-    void removePHIs(const MachineBasicBlock *origBB, std::vector<MachineBasicBlock *> &prologues, std::vector<MachineBasicBlock *> &epilogues, MachineBasicBlock *kernelBB, std::map<Value*, MachineBasicBlock*> &newValLocation);
+    void removePHIs(const MachineBasicBlock* SB, std::vector<MachineBasicBlock*> &prologues, std::vector<MachineBasicBlock *> &epilogues, MachineBasicBlock *kernelBB, std::map<Value*, MachineBasicBlock*> &newValLocation);
 
     void connectedComponentSet(MSchedGraphNode *node, std::set<MSchedGraphNode*> &ccSet, std::set<MSchedGraphNode*> &lastNodes);
 
diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.cpp b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.cpp
index bc18027ff4..80594c3451 100644
--- a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.cpp
+++ b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.cpp
@@ -17,12 +17,16 @@
 
 #include "DependenceAnalyzer.h"
 #include "ModuloSchedulingSuperBlock.h"
+#include "llvm/Constants.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/Support/CFG.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/GraphWriter.h"
+#include "llvm/Support/Timer.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/SCCIterator.h"
 #include "llvm/Instructions.h"
 #include "../MachineCodeForInstruction.h"
 #include "../SparcV9RegisterInfo.h"
@@ -30,6 +34,8 @@
 #include "../SparcV9TmpInstr.h"
 #include <fstream>
 #include <sstream>
+#include <cmath>
+#include <utility>
 
 using namespace llvm;
 /// Create ModuloSchedulingSBPass
@@ -39,9 +45,18 @@ FunctionPass *llvm::createModuloSchedulingSBPass(TargetMachine & targ) {
   return new ModuloSchedulingSBPass(targ);
 }
 
+
+#if 1
+#define TIME_REGION(VARNAME, DESC) \
+   NamedRegionTimer VARNAME(DESC)
+#else
+#define TIME_REGION(VARNAME, DESC)
+#endif
+
+
 //Graph Traits for printing out the dependence graph
 template<typename GraphType>
-static void WriteGraphToFile(std::ostream &O, const std::string &GraphName,
+static void WriteGraphToFileSB(std::ostream &O, const std::string &GraphName,
                              const GraphType &GT) {
   std::string Filename = GraphName + ".dot";
   O << "Writing '" << Filename << "'...";
@@ -58,8 +73,82 @@ namespace llvm {
   Statistic<> NumLoops("moduloschedSB-numLoops", "Total Number of Loops");
   Statistic<> NumSB("moduloschedSB-numSuperBlocks", "Total Number of SuperBlocks");
   Statistic<> BBWithCalls("modulosched-BBCalls", "Basic Blocks rejected due to calls");
-  Statistic<> BBWithCondMov("modulosched-loopCondMov", "Basic Blocks rejected due to conditional moves");
+  Statistic<> BBWithCondMov("modulosched-loopCondMov", 
+			    "Basic Blocks rejected due to conditional moves");
+  Statistic<> SBResourceConstraint("modulosched-resourceConstraint", 
+				 "Loops constrained by resources");
+  Statistic<> SBRecurrenceConstraint("modulosched-recurrenceConstraint", 
+				   "Loops constrained by recurrences");
+  Statistic<> SBFinalIISum("modulosched-finalIISum", "Sum of all final II");
+  Statistic<> SBIISum("modulosched-IISum", "Sum of all theoretical II");
+  Statistic<> SBMSLoops("modulosched-schedLoops", "Number of loops successfully modulo-scheduled");
+  Statistic<> SBNoSched("modulosched-noSched", "No schedule");
+  Statistic<> SBSameStage("modulosched-sameStage", "Max stage is 0");
+  Statistic<> SBBLoops("modulosched-SBBLoops", "Number single basic block loops");
+  Statistic<> SBInvalid("modulosched-SBInvalid", "Number invalid superblock loops");
+  Statistic<> SBValid("modulosched-SBValid", "Number valid superblock loops");
+ Statistic<> SBSize("modulosched-SBSize", "Total size of all valid superblocks");
+
+  template<>
+  struct DOTGraphTraits<MSchedGraphSB*> : public DefaultDOTGraphTraits {
+    static std::string getGraphName(MSchedGraphSB *F) {
+      return "Dependence Graph";
+    }
+
+    static std::string getNodeLabel(MSchedGraphSBNode *Node, MSchedGraphSB *Graph) {
+      if(!Node->isPredicate()) {
+	if (Node->getInst()) {
+	  std::stringstream ss;
+	  ss << *(Node->getInst());
+	  return ss.str(); //((MachineInstr*)Node->getInst());
+	}
+	else
+	  return "No Inst";
+      }
+      else
+	return "Pred Node";
+    }
+    static std::string getEdgeSourceLabel(MSchedGraphSBNode *Node,
+					  MSchedGraphSBNode::succ_iterator I) {
+      //Label each edge with the type of dependence
+      std::string edgelabel = "";
+      switch (I.getEdge().getDepOrderType()) {
+	
+      case MSchedGraphSBEdge::TrueDep:
+	edgelabel = "True";
+	break;
+
+      case MSchedGraphSBEdge::AntiDep:
+	edgelabel =  "Anti";
+	break;
+	
+      case MSchedGraphSBEdge::OutputDep:
+	edgelabel = "Output";
+	break;
+	
+      case MSchedGraphSBEdge::NonDataDep:
+	edgelabel = "Pred";
+	break;
+
+      default:
+	edgelabel = "Unknown";
+	break;
+      }
+
+      //FIXME
+      int iteDiff = I.getEdge().getIteDiff();
+      std::string intStr = "(IteDiff: ";
+      intStr += itostr(iteDiff);
+
+      intStr += ")";
+      edgelabel += intStr;
+
+      return edgelabel;
+    }
+  };
+
   bool ModuloSchedulingSBPass::runOnFunction(Function &F) {
+    alarm(100);
     bool Changed = false;