lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp

   1 //===-- ModuloScheduling.cpp - ModuloScheduling  ----------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This ModuloScheduling pass is based on the Swing Modulo Scheduling
  11 //  algorithm.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "ModuloSched"
  16
  17 #include "ModuloScheduling.h"
  18 #include "llvm/Instructions.h"
  19 #include "llvm/Function.h"
  20 #include "llvm/CodeGen/InstrSelection.h"
  21 #include "llvm/CodeGen/MachineFunction.h"
  22 #include "llvm/CodeGen/MachineCodeForInstruction.h"
  23 #include "llvm/CodeGen/Passes.h"
  24 #include "llvm/Support/CFG.h"
  25 #include "Support/Casting.h"
  26 #include "llvm/Target/TargetSchedInfo.h"
  27 #include "Support/Debug.h"
  28 #include "Support/GraphWriter.h"
  29 #include "Support/StringExtras.h"
  30 #include <cmath>
  31 #include <fstream>
  32 #include <sstream>
  33 #include <utility>
  34 #include <vector>
  35 #include "../../Target/SparcV9/SparcV9Internals.h"
  36 #include "../../Target/SparcV9/SparcV9RegisterInfo.h"
  37 using namespace llvm;
  38
  39 /// Create ModuloSchedulingPass
  40 ///
  41 FunctionPass *llvm::createModuloSchedulingPass(TargetMachine & targ) {
  42   DEBUG(std::cerr << "Created ModuloSchedulingPass\n");
  43   return new ModuloSchedulingPass(targ);
  44 }
  45
  46
  47 //Graph Traits for printing out the dependence graph
  48 template<typename GraphType>
  49 static void WriteGraphToFile(std::ostream &O, const std::string &GraphName,
  50                              const GraphType &GT) {
  51   std::string Filename = GraphName + ".dot";
  52   O << "Writing '" << Filename << "'...";
  53   std::ofstream F(Filename.c_str());
  54
  55   if (F.good())
  56     WriteGraph(F, GT);
  57   else
  58     O << "  error opening file for writing!";
  59   O << "\n";
  60 };
  61
  62 //Graph Traits for printing out the dependence graph
  63 namespace llvm {
  64
  65   template<>
  66   struct DOTGraphTraits<MSchedGraph*> : public DefaultDOTGraphTraits {
  67     static std::string getGraphName(MSchedGraph *F) {
  68       return "Dependence Graph";
  69     }
  70
  71     static std::string getNodeLabel(MSchedGraphNode *Node, MSchedGraph *Graph) {
  72       if (Node->getInst()) {
  73         std::stringstream ss;
  74         ss << *(Node->getInst());
  75         return ss.str(); //((MachineInstr*)Node->getInst());
  76       }
  77       else
  78         return "No Inst";
  79     }
  80     static std::string getEdgeSourceLabel(MSchedGraphNode *Node,
  81                                           MSchedGraphNode::succ_iterator I) {
  82       //Label each edge with the type of dependence
  83       std::string edgelabel = "";
  84       switch (I.getEdge().getDepOrderType()) {
  85
  86       case MSchedGraphEdge::TrueDep:
  87         edgelabel = "True";
  88         break;
  89
  90       case MSchedGraphEdge::AntiDep:
  91         edgelabel =  "Anti";
  92         break;
  93
  94       case MSchedGraphEdge::OutputDep:
  95         edgelabel = "Output";
  96         break;
  97
  98       default:
  99         edgelabel = "Unknown";
 100         break;
 101       }
 102
 103       //FIXME
 104       int iteDiff = I.getEdge().getIteDiff();
 105       std::string intStr = "(IteDiff: ";
 106       intStr += itostr(iteDiff);
 107
 108       intStr += ")";
 109       edgelabel += intStr;
 110
 111       return edgelabel;
 112     }
 113   };
 114 }
 115
 116 /// ModuloScheduling::runOnFunction - main transformation entry point
 117 /// The Swing Modulo Schedule algorithm has three basic steps:
 118 /// 1) Computation and Analysis of the dependence graph
 119 /// 2) Ordering of the nodes
 120 /// 3) Scheduling
 121 ///
 122 bool ModuloSchedulingPass::runOnFunction(Function &F) {
 123
 124   bool Changed = false;
 125
 126   DEBUG(std::cerr << "Creating ModuloSchedGraph for each valid BasicBlock in" + F.getName() + "\n");
 127
 128   //Get MachineFunction
 129   MachineFunction &MF = MachineFunction::get(&F);
 130
 131   //Print out machine function
 132   DEBUG(MF.print(std::cerr));
 133
 134   //Worklist
 135   std::vector<MachineBasicBlock*> Worklist;
 136
 137   //Iterate over BasicBlocks and put them into our worklist if they are valid
 138   for (MachineFunction::iterator BI = MF.begin(); BI != MF.end(); ++BI)
 139     if(MachineBBisValid(BI))
 140       Worklist.push_back(&*BI);
 141
 142
 143   //Iterate over the worklist and perform scheduling
 144   for(std::vector<MachineBasicBlock*>::iterator BI = Worklist.begin(),
 145         BE = Worklist.end(); BI != BE; ++BI) {
 146
 147     MSchedGraph *MSG = new MSchedGraph(*BI, target);
 148
 149     //Write Graph out to file
 150     DEBUG(WriteGraphToFile(std::cerr, F.getName(), MSG));
 151
 152     //Print out BB for debugging
 153     DEBUG((*BI)->print(std::cerr));
 154
 155     //Calculate Resource II
 156     int ResMII = calculateResMII(*BI);
 157
 158     //Calculate Recurrence II
 159     int RecMII = calculateRecMII(MSG, ResMII);
 160
 161     //Our starting initiation interval is the maximum of RecMII and ResMII
 162     II = std::max(RecMII, ResMII);
 163
 164     //Print out II, RecMII, and ResMII
 165     DEBUG(std::cerr << "II starts out as " << II << " ( RecMII=" << RecMII << "and ResMII=" << ResMII << "\n");
 166
 167     //Calculate Node Properties
 168     calculateNodeAttributes(MSG, ResMII);
 169
 170     //Dump node properties if in debug mode
 171     DEBUG(for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I =  nodeToAttributesMap.begin(),
 172                 E = nodeToAttributesMap.end(); I !=E; ++I) {
 173       std::cerr << "Node: " << *(I->first) << " ASAP: " << I->second.ASAP << " ALAP: "
 174                 << I->second.ALAP << " MOB: " << I->second.MOB << " Depth: " << I->second.depth
 175                 << " Height: " << I->second.height << "\n";
 176     });
 177
 178     //Put nodes in order to schedule them
 179     computePartialOrder();
 180
 181     //Dump out partial order
 182     DEBUG(for(std::vector<std::vector<MSchedGraphNode*> >::iterator I = partialOrder.begin(),
 183                 E = partialOrder.end(); I !=E; ++I) {
 184       std::cerr << "Start set in PO\n";
 185       for(std::vector<MSchedGraphNode*>::iterator J = I->begin(), JE = I->end(); J != JE; ++J)
 186         std::cerr << "PO:" << **J << "\n";
 187     });
 188
 189     //Place nodes in final order
 190     orderNodes();
 191
 192     //Dump out order of nodes
 193     DEBUG(for(std::vector<MSchedGraphNode*>::iterator I = FinalNodeOrder.begin(), E = FinalNodeOrder.end(); I != E; ++I) {
 194           std::cerr << "FO:" << **I << "\n";
 195     });
 196
 197     //Finally schedule nodes
 198     computeSchedule();
 199
 200     //Print out final schedule
 201     DEBUG(schedule.print(std::cerr));
 202
 203
 204     //Final scheduling step is to reconstruct the loop
 205     reconstructLoop(*BI);
 206
 207     //Print out new loop
 208
 209
 210     //Clear out our maps for the next basic block that is processed
 211     nodeToAttributesMap.clear();
 212     partialOrder.clear();
 213     recurrenceList.clear();
 214     FinalNodeOrder.clear();
 215     schedule.clear();
 216
 217     //Clean up. Nuke old MachineBB and llvmBB
 218     //BasicBlock *llvmBB = (BasicBlock*) (*BI)->getBasicBlock();
 219     //Function *parent = (Function*) llvmBB->getParent();
 220     //Should't std::find work??
 221     //parent->getBasicBlockList().erase(std::find(parent->getBasicBlockList().begin(), parent->getBasicBlockList().end(), *llvmBB));
 222     //parent->getBasicBlockList().erase(llvmBB);
 223
 224     //delete(llvmBB);
 225     //delete(*BI);
 226   }
 227
 228
 229   return Changed;
 230 }
 231
 232
 233 /// This function checks if a Machine Basic Block is valid for modulo
 234 /// scheduling. This means that it has no control flow (if/else or
 235 /// calls) in the block.  Currently ModuloScheduling only works on
 236 /// single basic block loops.
 237 bool ModuloSchedulingPass::MachineBBisValid(const MachineBasicBlock *BI) {
 238
 239   bool isLoop = false;
 240
 241   //Check first if its a valid loop
 242   for(succ_const_iterator I = succ_begin(BI->getBasicBlock()),
 243         E = succ_end(BI->getBasicBlock()); I != E; ++I) {
 244     if (*I == BI->getBasicBlock())    // has single block loop
 245       isLoop = true;
 246   }
 247
 248   if(!isLoop)
 249     return false;
 250
 251   //Get Target machine instruction info
 252   const TargetInstrInfo *TMI = target.getInstrInfo();
 253
 254   //Check each instruction and look for calls
 255   for(MachineBasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I) {
 256     //Get opcode to check instruction type
 257     MachineOpCode OC = I->getOpcode();
 258     if(TMI->isCall(OC))
 259       return false;
 260
 261   }
 262   return true;
 263
 264 }
 265
 266 //ResMII is calculated by determining the usage count for each resource
 267 //and using the maximum.
 268 //FIXME: In future there should be a way to get alternative resources
 269 //for each instruction
 270 int ModuloSchedulingPass::calculateResMII(const MachineBasicBlock *BI) {
 271
 272   const TargetInstrInfo *mii = target.getInstrInfo();
 273   const TargetSchedInfo *msi = target.getSchedInfo();
 274
 275   int ResMII = 0;
 276
 277   //Map to keep track of usage count of each resource
 278   std::map<unsigned, unsigned> resourceUsageCount;
 279
 280   for(MachineBasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I) {
 281
 282     //Get resource usage for this instruction
 283     InstrRUsage rUsage = msi->getInstrRUsage(I->getOpcode());
 284     std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
 285
 286     //Loop over resources in each cycle and increments their usage count
 287     for(unsigned i=0; i < resources.size(); ++i)
 288       for(unsigned j=0; j < resources[i].size(); ++j) {
 289         if( resourceUsageCount.find(resources[i][j]) == resourceUsageCount.end()) {
 290           resourceUsageCount[resources[i][j]] = 1;
 291         }
 292         else {
 293           resourceUsageCount[resources[i][j]] =  resourceUsageCount[resources[i][j]] + 1;
 294         }
 295       }
 296   }
 297
 298   //Find maximum usage count
 299
 300   //Get max number of instructions that can be issued at once. (FIXME)
 301   int issueSlots = msi->maxNumIssueTotal;
 302
 303   for(std::map<unsigned,unsigned>::iterator RB = resourceUsageCount.begin(), RE = resourceUsageCount.end(); RB != RE; ++RB) {
 304
 305     //Get the total number of the resources in our cpu
 306     int resourceNum = CPUResource::getCPUResource(RB->first)->maxNumUsers;
 307
 308     //Get total usage count for this resources
 309     unsigned usageCount = RB->second;
 310
 311     //Divide the usage count by either the max number we can issue or the number of
 312     //resources (whichever is its upper bound)
 313     double finalUsageCount;
 314     if( resourceNum <= issueSlots)
 315       finalUsageCount = ceil(1.0 * usageCount / resourceNum);
 316     else
 317       finalUsageCount = ceil(1.0 * usageCount / issueSlots);
 318
 319
 320     //Only keep track of the max
 321     ResMII = std::max( (int) finalUsageCount, ResMII);
 322
 323   }
 324
 325   return ResMII;
 326
 327 }
 328
 329 /// calculateRecMII - Calculates the value of the highest recurrence
 330 /// By value we mean the total latency
 331 int ModuloSchedulingPass::calculateRecMII(MSchedGraph *graph, int MII) {
 332   std::vector<MSchedGraphNode*> vNodes;
 333   //Loop over all nodes in the graph
 334   for(MSchedGraph::iterator I = graph->begin(), E = graph->end(); I != E; ++I) {
 335     findAllReccurrences(I->second, vNodes, MII);
 336     vNodes.clear();
 337   }
 338
 339   int RecMII = 0;
 340
 341   for(std::set<std::pair<int, std::vector<MSchedGraphNode*> > >::iterator I = recurrenceList.begin(), E=recurrenceList.end(); I !=E; ++I) {
 342     DEBUG(for(std::vector<MSchedGraphNode*>::const_iterator N = I->second.begin(), NE = I->second.end(); N != NE; ++N) {
 343       std::cerr << **N << "\n";
 344     });
 345     RecMII = std::max(RecMII, I->first);
 346   }
 347
 348   return MII;
 349 }
 350
 351 /// calculateNodeAttributes - The following properties are calculated for
 352 /// each node in the dependence graph: ASAP, ALAP, Depth, Height, and
 353 /// MOB.
 354 void ModuloSchedulingPass::calculateNodeAttributes(MSchedGraph *graph, int MII) {
 355
 356   //Loop over the nodes and add them to the map
 357   for(MSchedGraph::iterator I = graph->begin(), E = graph->end(); I != E; ++I) {
 358     //Assert if its already in the map
 359     assert(nodeToAttributesMap.find(I->second) == nodeToAttributesMap.end() && "Node attributes are already in the map");
 360
 361     //Put into the map with default attribute values
 362     nodeToAttributesMap[I->second] = MSNodeAttributes();
 363   }
 364
 365   //Create set to deal with reccurrences
 366   std::set<MSchedGraphNode*> visitedNodes;
 367
 368   //Now Loop over map and calculate the node attributes
 369   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
 370     calculateASAP(I->first, MII, (MSchedGraphNode*) 0);
 371     visitedNodes.clear();
 372   }
 373
 374   int maxASAP = findMaxASAP();
 375   //Calculate ALAP which depends on ASAP being totally calculated
 376   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
 377     calculateALAP(I->first, MII, maxASAP, (MSchedGraphNode*) 0);
 378     visitedNodes.clear();
 379   }
 380
 381   //Calculate MOB which depends on ASAP being totally calculated, also do depth and height
 382   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
 383     (I->second).MOB = std::max(0,(I->second).ALAP - (I->second).ASAP);
 384
 385     DEBUG(std::cerr << "MOB: " << (I->second).MOB << " (" << *(I->first) << ")\n");
 386     calculateDepth(I->first, (MSchedGraphNode*) 0);
 387     calculateHeight(I->first, (MSchedGraphNode*) 0);
 388   }
 389
 390
 391 }
 392
 393 /// ignoreEdge - Checks to see if this edge of a recurrence should be ignored or not
 394 bool ModuloSchedulingPass::ignoreEdge(MSchedGraphNode *srcNode, MSchedGraphNode *destNode) {
 395   if(destNode == 0 || srcNode ==0)
 396     return false;
 397
 398   bool findEdge = edgesToIgnore.count(std::make_pair(srcNode, destNode->getInEdgeNum(srcNode)));
 399
 400   return findEdge;
 401 }
 402
 403
 404 /// calculateASAP - Calculates the
 405 int  ModuloSchedulingPass::calculateASAP(MSchedGraphNode *node, int MII, MSchedGraphNode *destNode) {
 406
 407   DEBUG(std::cerr << "Calculating ASAP for " << *node << "\n");
 408
 409   //Get current node attributes
 410   MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second;
 411
 412   if(attributes.ASAP != -1)
 413     return attributes.ASAP;
 414
 415   int maxPredValue = 0;
 416
 417   //Iterate over all of the predecessors and find max
 418   for(MSchedGraphNode::pred_iterator P = node->pred_begin(), E = node->pred_end(); P != E; ++P) {
 419
 420     //Only process if we are not ignoring the edge
 421     if(!ignoreEdge(*P, node)) {
 422       int predASAP = -1;
 423       predASAP = calculateASAP(*P, MII, node);
 424
 425       assert(predASAP != -1 && "ASAP has not been calculated");
 426       int iteDiff = node->getInEdge(*P).getIteDiff();
 427
 428       int currentPredValue = predASAP + (*P)->getLatency() - (iteDiff * MII);
 429       DEBUG(std::cerr << "pred ASAP: " << predASAP << ", iteDiff: " << iteDiff << ", PredLatency: " << (*P)->getLatency() << ", Current ASAP pred: " << currentPredValue << "\n");
 430       maxPredValue = std::max(maxPredValue, currentPredValue);
 431     }
 432   }
 433
 434   attributes.ASAP = maxPredValue;
 435
 436   DEBUG(std::cerr << "ASAP: " << attributes.ASAP << " (" << *node << ")\n");
 437
 438   return maxPredValue;
 439 }
 440
 441
 442 int ModuloSchedulingPass::calculateALAP(MSchedGraphNode *node, int MII,
 443                                         int maxASAP, MSchedGraphNode *srcNode) {
 444
 445   DEBUG(std::cerr << "Calculating ALAP for " << *node << "\n");
 446
 447   MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second;
 448
 449   if(attributes.ALAP != -1)
 450     return attributes.ALAP;
 451
 452   if(node->hasSuccessors()) {
 453
 454     //Trying to deal with the issue where the node has successors, but
 455     //we are ignoring all of the edges to them. So this is my hack for
 456     //now.. there is probably a more elegant way of doing this (FIXME)
 457     bool processedOneEdge = false;
 458
 459     //FIXME, set to something high to start
 460     int minSuccValue = 9999999;
 461
 462     //Iterate over all of the predecessors and fine max
 463     for(MSchedGraphNode::succ_iterator P = node->succ_begin(),
 464           E = node->succ_end(); P != E; ++P) {
 465
 466       //Only process if we are not ignoring the edge
 467       if(!ignoreEdge(node, *P)) {
 468         processedOneEdge = true;
 469         int succALAP = -1;
 470         succALAP = calculateALAP(*P, MII, maxASAP, node);
 471
 472         assert(succALAP != -1 && "Successors ALAP should have been caclulated");
 473
 474         int iteDiff = P.getEdge().getIteDiff();
 475
 476         int currentSuccValue = succALAP - node->getLatency() + iteDiff * MII;
 477
 478         DEBUG(std::cerr << "succ ALAP: " << succALAP << ", iteDiff: " << iteDiff << ", SuccLatency: " << (*P)->getLatency() << ", Current ALAP succ: " << currentSuccValue << "\n");
 479
 480         minSuccValue = std::min(minSuccValue, currentSuccValue);
 481       }
 482     }
 483
 484     if(processedOneEdge)
 485         attributes.ALAP = minSuccValue;
 486
 487     else
 488       attributes.ALAP = maxASAP;
 489   }
 490   else
 491     attributes.ALAP = maxASAP;
 492
 493   DEBUG(std::cerr << "ALAP: " << attributes.ALAP << " (" << *node << ")\n");
 494
 495   if(attributes.ALAP < 0)
 496     attributes.ALAP = 0;
 497
 498   return attributes.ALAP;
 499 }
 500
 501 int ModuloSchedulingPass::findMaxASAP() {
 502   int maxASAP = 0;
 503
 504   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(),
 505         E = nodeToAttributesMap.end(); I != E; ++I)
 506     maxASAP = std::max(maxASAP, I->second.ASAP);
 507   return maxASAP;
 508 }
 509
 510
 511 int ModuloSchedulingPass::calculateHeight(MSchedGraphNode *node,MSchedGraphNode *srcNode) {
 512
 513   MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second;
 514
 515   if(attributes.height != -1)
 516     return attributes.height;
 517
 518   int maxHeight = 0;
 519
 520   //Iterate over all of the predecessors and find max
 521   for(MSchedGraphNode::succ_iterator P = node->succ_begin(),
 522         E = node->succ_end(); P != E; ++P) {
 523
 524
 525     if(!ignoreEdge(node, *P)) {
 526       int succHeight = calculateHeight(*P, node);
 527
 528       assert(succHeight != -1 && "Successors Height should have been caclulated");
 529
 530       int currentHeight = succHeight + node->getLatency();
 531       maxHeight = std::max(maxHeight, currentHeight);
 532     }
 533   }
 534   attributes.height = maxHeight;
 535   DEBUG(std::cerr << "Height: " << attributes.height << " (" << *node << ")\n");
 536   return maxHeight;
 537 }
 538
 539
 540 int ModuloSchedulingPass::calculateDepth(MSchedGraphNode *node,
 541                                           MSchedGraphNode *destNode) {
 542
 543   MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second;
 544
 545   if(attributes.depth != -1)
 546     return attributes.depth;
 547
 548   int maxDepth = 0;
 549
 550   //Iterate over all of the predecessors and fine max
 551   for(MSchedGraphNode::pred_iterator P = node->pred_begin(), E = node->pred_end(); P != E; ++P) {
 552
 553     if(!ignoreEdge(*P, node)) {
 554       int predDepth = -1;
 555       predDepth = calculateDepth(*P, node);
 556
 557       assert(predDepth != -1 && "Predecessors ASAP should have been caclulated");
 558
 559       int currentDepth = predDepth + (*P)->getLatency();
 560       maxDepth = std::max(maxDepth, currentDepth);
 561     }
 562   }
 563   attributes.depth = maxDepth;
 564
 565   DEBUG(std::cerr << "Depth: " << attributes.depth << " (" << *node << "*)\n");
 566   return maxDepth;
 567 }
 568
 569
 570
 571 void ModuloSchedulingPass::addReccurrence(std::vector<MSchedGraphNode*> &recurrence, int II, MSchedGraphNode *srcBENode, MSchedGraphNode *destBENode) {
 572   //Check to make sure that this recurrence is unique
 573   bool same = false;
 574
 575
 576   //Loop over all recurrences already in our list
 577   for(std::set<std::pair<int, std::vector<MSchedGraphNode*> > >::iterator R = recurrenceList.begin(), RE = recurrenceList.end(); R != RE; ++R) {
 578
 579     bool all_same = true;
 580      //First compare size
 581     if(R->second.size() == recurrence.size()) {
 582
 583       for(std::vector<MSchedGraphNode*>::const_iterator node = R->second.begin(), end = R->second.end(); node != end; ++node) {
 584         if(find(recurrence.begin(), recurrence.end(), *node) == recurrence.end()) {
 585           all_same = all_same && false;
 586           break;
 587         }
 588         else
 589           all_same = all_same && true;
 590       }
 591       if(all_same) {
 592         same = true;
 593         break;
 594       }
 595     }
 596   }
 597
 598   if(!same) {
 599     srcBENode = recurrence.back();
 600     destBENode = recurrence.front();
 601
 602     //FIXME
 603     if(destBENode->getInEdge(srcBENode).getIteDiff() == 0) {
 604       //DEBUG(std::cerr << "NOT A BACKEDGE\n");
 605       //find actual backedge HACK HACK
 606       for(unsigned i=0; i< recurrence.size()-1; ++i) {
 607         if(recurrence[i+1]->getInEdge(recurrence[i]).getIteDiff() == 1) {
 608           srcBENode = recurrence[i];
 609           destBENode = recurrence[i+1];
 610           break;
 611         }
 612
 613       }
 614
 615     }
 616     DEBUG(std::cerr << "Back Edge to Remove: " << *srcBENode << " to " << *destBENode << "\n");
 617     edgesToIgnore.insert(std::make_pair(srcBENode, destBENode->getInEdgeNum(srcBENode)));
 618     recurrenceList.insert(std::make_pair(II, recurrence));
 619   }
 620
 621 }
 622
 623 void ModuloSchedulingPass::findAllReccurrences(MSchedGraphNode *node,
 624                                                std::vector<MSchedGraphNode*> &visitedNodes,
 625                                                int II) {
 626
 627   if(find(visitedNodes.begin(), visitedNodes.end(), node) != visitedNodes.end()) {
 628     std::vector<MSchedGraphNode*> recurrence;
 629     bool first = true;
 630     int delay = 0;
 631     int distance = 0;
 632     int RecMII = II; //Starting value
 633     MSchedGraphNode *last = node;
 634     MSchedGraphNode *srcBackEdge;
 635     MSchedGraphNode *destBackEdge;
 636
 637
 638
 639     for(std::vector<MSchedGraphNode*>::iterator I = visitedNodes.begin(), E = visitedNodes.end();
 640         I !=E; ++I) {
 641
 642       if(*I == node)
 643         first = false;
 644       if(first)
 645         continue;
 646
 647       delay = delay + (*I)->getLatency();
 648
 649       if(*I != node) {
 650         int diff = (*I)->getInEdge(last).getIteDiff();
 651         distance += diff;
 652         if(diff > 0) {
 653           srcBackEdge = last;
 654           destBackEdge = *I;
 655         }
 656       }
 657
 658       recurrence.push_back(*I);
 659       last = *I;
 660     }
 661
 662
 663
 664     //Get final distance calc
 665     distance += node->getInEdge(last).getIteDiff();
 666
 667
 668     //Adjust II until we get close to the inequality delay - II*distance <= 0
 669
 670     int value = delay-(RecMII * distance);
 671     int lastII = II;
 672     while(value <= 0) {
 673
 674       lastII = RecMII;
 675       RecMII--;
 676       value = delay-(RecMII * distance);
 677     }
 678
 679
 680     DEBUG(std::cerr << "Final II for this recurrence: " << lastII << "\n");
 681     addReccurrence(recurrence, lastII, srcBackEdge, destBackEdge);
 682     assert(distance != 0 && "Recurrence distance should not be zero");
 683     return;
 684   }
 685
 686   for(MSchedGraphNode::succ_iterator I = node->succ_begin(), E = node->succ_end(); I != E; ++I) {
 687     visitedNodes.push_back(node);
 688     findAllReccurrences(*I, visitedNodes, II);
 689     visitedNodes.pop_back();
 690   }
 691 }
 692
 693
 694
 695
 696
 697 void ModuloSchedulingPass::computePartialOrder() {
 698
 699
 700   //Loop over all recurrences and add to our partial order
 701   //be sure to remove nodes that are already in the partial order in
 702   //a different recurrence and don't add empty recurrences.
 703   for(std::set<std::pair<int, std::vector<MSchedGraphNode*> > >::reverse_iterator I = recurrenceList.rbegin(), E=recurrenceList.rend(); I !=E; ++I) {
 704
 705     //Add nodes that connect this recurrence to the previous recurrence
 706
 707     //If this is the first recurrence in the partial order, add all predecessors
 708     for(std::vector<MSchedGraphNode*>::const_iterator N = I->second.begin(), NE = I->second.end(); N != NE; ++N) {
 709
 710     }
 711
 712
 713     std::vector<MSchedGraphNode*> new_recurrence;
 714     //Loop through recurrence and remove any nodes already in the partial order
 715     for(std::vector<MSchedGraphNode*>::const_iterator N = I->second.begin(), NE = I->second.end(); N != NE; ++N) {
 716       bool found = false;
 717       for(std::vector<std::vector<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), PE = partialOrder.end(); PO != PE; ++PO) {
 718         if(find(PO->begin(), PO->end(), *N) != PO->end())
 719           found = true;
 720       }
 721       if(!found) {
 722         new_recurrence.push_back(*N);
 723
 724         if(partialOrder.size() == 0)
 725           //For each predecessors, add it to this recurrence ONLY if it is not already in it
 726           for(MSchedGraphNode::pred_iterator P = (*N)->pred_begin(),
 727                 PE = (*N)->pred_end(); P != PE; ++P) {
 728
 729             //Check if we are supposed to ignore this edge or not
 730             if(!ignoreEdge(*P, *N))
 731               //Check if already in this recurrence
 732               if(find(I->second.begin(), I->second.end(), *P) == I->second.end()) {
 733                 //Also need to check if in partial order
 734                 bool predFound = false;
 735                 for(std::vector<std::vector<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), PEND = partialOrder.end(); PO != PEND; ++PO) {
 736                   if(find(PO->begin(), PO->end(), *P) != PO->end())
 737                     predFound = true;
 738                 }
 739
 740                 if(!predFound)
 741                   if(find(new_recurrence.begin(), new_recurrence.end(), *P) == new_recurrence.end())
 742                      new_recurrence.push_back(*P);
 743
 744               }
 745           }
 746       }
 747     }
 748
 749
 750     if(new_recurrence.size() > 0)
 751       partialOrder.push_back(new_recurrence);
 752   }
 753
 754   //Add any nodes that are not already in the partial order
 755   std::vector<MSchedGraphNode*> lastNodes;
 756   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
 757     bool found = false;
 758     //Check if its already in our partial order, if not add it to the final vector
 759     for(std::vector<std::vector<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), PE = partialOrder.end(); PO != PE; ++PO) {
 760       if(find(PO->begin(), PO->end(), I->first) != PO->end())
 761         found = true;
 762     }
 763     if(!found)
 764       lastNodes.push_back(I->first);
 765   }
 766
 767   if(lastNodes.size() > 0)
 768     partialOrder.push_back(lastNodes);
 769
 770 }
 771
 772
 773 void ModuloSchedulingPass::predIntersect(std::vector<MSchedGraphNode*> &CurrentSet, std::vector<MSchedGraphNode*> &IntersectResult) {
 774
 775   //Sort CurrentSet so we can use lowerbound
 776   sort(CurrentSet.begin(), CurrentSet.end());
 777
 778   for(unsigned j=0; j < FinalNodeOrder.size(); ++j) {
 779     for(MSchedGraphNode::pred_iterator P = FinalNodeOrder[j]->pred_begin(),
 780           E = FinalNodeOrder[j]->pred_end(); P != E; ++P) {
 781
 782       //Check if we are supposed to ignore this edge or not
 783       if(ignoreEdge(*P,FinalNodeOrder[j]))
 784         continue;
 785
 786       if(find(CurrentSet.begin(),
 787                      CurrentSet.end(), *P) != CurrentSet.end())
 788         if(find(FinalNodeOrder.begin(), FinalNodeOrder.end(), *P) == FinalNodeOrder.end())
 789           IntersectResult.push_back(*P);
 790     }
 791   }
 792 }
 793
 794 void ModuloSchedulingPass::succIntersect(std::vector<MSchedGraphNode*> &CurrentSet, std::vector<MSchedGraphNode*> &IntersectResult) {
 795
 796   //Sort CurrentSet so we can use lowerbound
 797   sort(CurrentSet.begin(), CurrentSet.end());
 798
 799   for(unsigned j=0; j < FinalNodeOrder.size(); ++j) {
 800     for(MSchedGraphNode::succ_iterator P = FinalNodeOrder[j]->succ_begin(),
 801           E = FinalNodeOrder[j]->succ_end(); P != E; ++P) {
 802
 803       //Check if we are supposed to ignore this edge or not
 804       if(ignoreEdge(FinalNodeOrder[j],*P))
 805         continue;
 806
 807       if(find(CurrentSet.begin(),
 808                      CurrentSet.end(), *P) != CurrentSet.end())
 809         if(find(FinalNodeOrder.begin(), FinalNodeOrder.end(), *P) == FinalNodeOrder.end())
 810           IntersectResult.push_back(*P);
 811     }
 812   }
 813 }
 814
 815 void dumpIntersection(std::vector<MSchedGraphNode*> &IntersectCurrent) {
 816   std::cerr << "Intersection (";
 817   for(std::vector<MSchedGraphNode*>::iterator I = IntersectCurrent.begin(), E = IntersectCurrent.end(); I != E; ++I)
 818     std::cerr << **I << ", ";
 819   std::cerr << ")\n";
 820 }
 821
 822
 823
 824 void ModuloSchedulingPass::orderNodes() {
 825
 826   int BOTTOM_UP = 0;
 827   int TOP_DOWN = 1;
 828
 829   //Set default order
 830   int order = BOTTOM_UP;
 831
 832
 833   //Loop over all the sets and place them in the final node order
 834   for(std::vector<std::vector<MSchedGraphNode*> >::iterator CurrentSet = partialOrder.begin(), E= partialOrder.end(); CurrentSet != E; ++CurrentSet) {
 835
 836     DEBUG(std::cerr << "Processing set in S\n");
 837     DEBUG(dumpIntersection(*CurrentSet));
 838
 839     //Result of intersection
 840     std::vector<MSchedGraphNode*> IntersectCurrent;
 841
 842     predIntersect(*CurrentSet, IntersectCurrent);
 843
 844     //If the intersection of predecessor and current set is not empty
 845     //sort nodes bottom up
 846     if(IntersectCurrent.size() != 0) {
 847       DEBUG(std::cerr << "Final Node Order Predecessors and Current Set interesection is NOT empty\n");
 848       order = BOTTOM_UP;
 849     }
 850     //If empty, use successors
 851     else {
 852       DEBUG(std::cerr << "Final Node Order Predecessors and Current Set interesection is empty\n");
 853
 854       succIntersect(*CurrentSet, IntersectCurrent);
 855
 856       //sort top-down
 857       if(IntersectCurrent.size() != 0) {
 858          DEBUG(std::cerr << "Final Node Order Successors and Current Set interesection is NOT empty\n");
 859         order = TOP_DOWN;
 860       }
 861       else {
 862         DEBUG(std::cerr << "Final Node Order Successors and Current Set interesection is empty\n");
 863         //Find node with max ASAP in current Set
 864         MSchedGraphNode *node;
 865         int maxASAP = 0;
 866         DEBUG(std::cerr << "Using current set of size " << CurrentSet->size() << "to find max ASAP\n");
 867         for(unsigned j=0; j < CurrentSet->size(); ++j) {
 868           //Get node attributes
 869           MSNodeAttributes nodeAttr= nodeToAttributesMap.find((*CurrentSet)[j])->second;
 870           //assert(nodeAttr != nodeToAttributesMap.end() && "Node not in attributes map!");
 871           DEBUG(std::cerr << "CurrentSet index " << j << "has ASAP: " << nodeAttr.ASAP << "\n");
 872           if(maxASAP < nodeAttr.ASAP) {
 873             maxASAP = nodeAttr.ASAP;
 874             node = (*CurrentSet)[j];
 875           }
 876         }
 877         assert(node != 0 && "In node ordering node should not be null");
 878         IntersectCurrent.push_back(node);
 879         order = BOTTOM_UP;
 880       }
 881     }
 882
 883     //Repeat until all nodes are put into the final order from current set
 884     while(IntersectCurrent.size() > 0) {
 885
 886       if(order == TOP_DOWN) {
 887         DEBUG(std::cerr << "Order is TOP DOWN\n");
 888
 889         while(IntersectCurrent.size() > 0) {
 890           DEBUG(std::cerr << "Intersection is not empty, so find heighest height\n");
 891
 892           int MOB = 0;
 893           int height = 0;
 894           MSchedGraphNode *highestHeightNode = IntersectCurrent[0];
 895
 896           //Find node in intersection with highest heigh and lowest MOB
 897           for(std::vector<MSchedGraphNode*>::iterator I = IntersectCurrent.begin(),
 898                 E = IntersectCurrent.end(); I != E; ++I) {
 899
 900             //Get current nodes properties
 901             MSNodeAttributes nodeAttr= nodeToAttributesMap.find(*I)->second;
 902
 903             if(height < nodeAttr.height) {
 904               highestHeightNode = *I;
 905               height = nodeAttr.height;
 906               MOB = nodeAttr.MOB;
 907             }
 908             else if(height ==  nodeAttr.height) {
 909               if(MOB > nodeAttr.height) {
 910                 highestHeightNode = *I;
 911                 height =  nodeAttr.height;
 912                 MOB = nodeAttr.MOB;
 913               }
 914             }
 915           }
 916
 917           //Append our node with greatest height to the NodeOrder
 918           if(find(FinalNodeOrder.begin(), FinalNodeOrder.end(), highestHeightNode) == FinalNodeOrder.end()) {
 919             DEBUG(std::cerr << "Adding node to Final Order: " << *highestHeightNode << "\n");
 920             FinalNodeOrder.push_back(highestHeightNode);
 921           }
 922
 923           //Remove V from IntersectOrder
 924           IntersectCurrent.erase(find(IntersectCurrent.begin(),
 925                                       IntersectCurrent.end(), highestHeightNode));
 926
 927
 928           //Intersect V's successors with CurrentSet
 929           for(MSchedGraphNode::succ_iterator P = highestHeightNode->succ_begin(),
 930                 E = highestHeightNode->succ_end(); P != E; ++P) {
 931             //if(lower_bound(CurrentSet->begin(),
 932             //     CurrentSet->end(), *P) != CurrentSet->end()) {
 933             if(find(CurrentSet->begin(), CurrentSet->end(), *P) != CurrentSet->end()) {
 934               if(ignoreEdge(highestHeightNode, *P))
 935                 continue;
 936               //If not already in Intersect, add
 937               if(find(IntersectCurrent.begin(), IntersectCurrent.end(), *P) == IntersectCurrent.end())
 938                 IntersectCurrent.push_back(*P);
 939             }
 940           }
 941         } //End while loop over Intersect Size
 942
 943         //Change direction
 944         order = BOTTOM_UP;
 945
 946         //Reset Intersect to reflect changes in OrderNodes
 947         IntersectCurrent.clear();
 948         predIntersect(*CurrentSet, IntersectCurrent);
 949
 950       } //End If TOP_DOWN
 951
 952         //Begin if BOTTOM_UP
 953       else {
 954         DEBUG(std::cerr << "Order is BOTTOM UP\n");
 955         while(IntersectCurrent.size() > 0) {
 956           DEBUG(std::cerr << "Intersection of size " << IntersectCurrent.size() << ", finding highest depth\n");
 957
 958           //dump intersection
 959           DEBUG(dumpIntersection(IntersectCurrent));
 960           //Get node with highest depth, if a tie, use one with lowest
 961           //MOB
 962           int MOB = 0;
 963           int depth = 0;
 964           MSchedGraphNode *highestDepthNode = IntersectCurrent[0];
 965
 966           for(std::vector<MSchedGraphNode*>::iterator I = IntersectCurrent.begin(),
 967                 E = IntersectCurrent.end(); I != E; ++I) {
 968             //Find node attribute in graph
 969             MSNodeAttributes nodeAttr= nodeToAttributesMap.find(*I)->second;
 970
 971             if(depth < nodeAttr.depth) {
 972               highestDepthNode = *I;
 973               depth = nodeAttr.depth;
 974               MOB = nodeAttr.MOB;
 975             }
 976             else if(depth == nodeAttr.depth) {
 977               if(MOB > nodeAttr.MOB) {
 978                 highestDepthNode = *I;
 979                 depth = nodeAttr.depth;
 980                 MOB = nodeAttr.MOB;
 981               }
 982             }
 983           }
 984
 985
 986
 987           //Append highest depth node to the NodeOrder
 988            if(find(FinalNodeOrder.begin(), FinalNodeOrder.end(), highestDepthNode) == FinalNodeOrder.end()) {
 989              DEBUG(std::cerr << "Adding node to Final Order: " << *highestDepthNode << "\n");
 990              FinalNodeOrder.push_back(highestDepthNode);
 991            }
 992           //Remove heightestDepthNode from IntersectOrder
 993           IntersectCurrent.erase(find(IntersectCurrent.begin(),
 994                                       IntersectCurrent.end(),highestDepthNode));
 995
 996
 997           //Intersect heightDepthNode's pred with CurrentSet
 998           for(MSchedGraphNode::pred_iterator P = highestDepthNode->pred_begin(),
 999                 E = highestDepthNode->pred_end(); P != E; ++P) {
1000             //if(lower_bound(CurrentSet->begin(),
1001             //     CurrentSet->end(), *P) != CurrentSet->end()) {
1002             if(find(CurrentSet->begin(), CurrentSet->end(), *P) != CurrentSet->end()) {
1003
1004               if(ignoreEdge(*P, highestDepthNode))
1005                 continue;
1006
1007             //If not already in Intersect, add
1008             if(find(IntersectCurrent.begin(),
1009                       IntersectCurrent.end(), *P) == IntersectCurrent.end())
1010                 IntersectCurrent.push_back(*P);
1011             }
1012           }
1013
1014         } //End while loop over Intersect Size
1015
1016           //Change order
1017         order = TOP_DOWN;
1018
1019         //Reset IntersectCurrent to reflect changes in OrderNodes
1020         IntersectCurrent.clear();
1021         succIntersect(*CurrentSet, IntersectCurrent);
1022         } //End if BOTTOM_DOWN
1023
1024     }
1025     //End Wrapping while loop
1026
1027   }//End for over all sets of nodes
1028
1029   //Return final Order
1030   //return FinalNodeOrder;
1031 }
1032
1033 void ModuloSchedulingPass::computeSchedule() {
1034
1035   bool success = false;
1036
1037   while(!success) {
1038
1039     //Loop over the final node order and process each node
1040     for(std::vector<MSchedGraphNode*>::iterator I = FinalNodeOrder.begin(),
1041           E = FinalNodeOrder.end(); I != E; ++I) {
1042
1043       //CalculateEarly and Late start
1044       int EarlyStart = -1;
1045       int LateStart = 99999; //Set to something higher then we would ever expect (FIXME)
1046       bool hasSucc = false;
1047       bool hasPred = false;
1048
1049       if(!(*I)->isBranch()) {
1050         //Loop over nodes in the schedule and determine if they are predecessors
1051         //or successors of the node we are trying to schedule
1052         for(MSSchedule::schedule_iterator nodesByCycle = schedule.begin(), nodesByCycleEnd = schedule.end();
1053             nodesByCycle != nodesByCycleEnd; ++nodesByCycle) {
1054
1055           //For this cycle, get the vector of nodes schedule and loop over it
1056           for(std::vector<MSchedGraphNode*>::iterator schedNode = nodesByCycle->second.begin(), SNE = nodesByCycle->second.end(); schedNode != SNE; ++schedNode) {
1057
1058             if((*I)->isPredecessor(*schedNode)) {
1059               if(!ignoreEdge(*schedNode, *I)) {
1060                 int diff = (*I)->getInEdge(*schedNode).getIteDiff();
1061                 int ES_Temp = nodesByCycle->first + (*schedNode)->getLatency() - diff * II;
1062                 DEBUG(std::cerr << "Diff: " << diff << " Cycle: " << nodesByCycle->first << "\n");
1063                 DEBUG(std::cerr << "Temp EarlyStart: " << ES_Temp << " Prev EarlyStart: " << EarlyStart << "\n");
1064                 EarlyStart = std::max(EarlyStart, ES_Temp);
1065                 hasPred = true;
1066               }
1067             }
1068             if((*I)->isSuccessor(*schedNode)) {
1069               if(!ignoreEdge(*I,*schedNode)) {
1070                 int diff = (*schedNode)->getInEdge(*I).getIteDiff();
1071                 int LS_Temp = nodesByCycle->first - (*I)->getLatency() + diff * II;
1072                 DEBUG(std::cerr << "Diff: " << diff << " Cycle: " << nodesByCycle->first << "\n");
1073                 DEBUG(std::cerr << "Temp LateStart: " << LS_Temp << " Prev LateStart: " << LateStart << "\n");
1074                 LateStart = std::min(LateStart, LS_Temp);
1075                 hasSucc = true;
1076               }
1077             }
1078           }
1079         }
1080       }
1081       else {
1082         //WARNING: HACK! FIXME!!!!
1083         EarlyStart = II-1;
1084         LateStart = II-1;
1085         hasPred = 1;
1086         hasSucc = 1;
1087       }
1088
1089
1090       DEBUG(std::cerr << "Has Successors: " << hasSucc << ", Has Pred: " << hasPred << "\n");
1091       DEBUG(std::cerr << "EarlyStart: " << EarlyStart << ", LateStart: " << LateStart << "\n");
1092
1093       //Check if the node has no pred or successors and set Early Start to its ASAP
1094       if(!hasSucc && !hasPred)
1095         EarlyStart = nodeToAttributesMap.find(*I)->second.ASAP;
1096
1097       //Now, try to schedule this node depending upon its pred and successor in the schedule
1098       //already
1099       if(!hasSucc && hasPred)
1100         success = scheduleNode(*I, EarlyStart, (EarlyStart + II -1));
1101       else if(!hasPred && hasSucc)
1102         success = scheduleNode(*I, LateStart, (LateStart - II +1));
1103       else if(hasPred && hasSucc)
1104         success = scheduleNode(*I, EarlyStart, std::min(LateStart, (EarlyStart + II -1)));
1105       else
1106         success = scheduleNode(*I, EarlyStart, EarlyStart + II - 1);
1107
1108       if(!success) {
1109         ++II;
1110         schedule.clear();
1111         break;
1112       }
1113
1114     }
1115
1116     DEBUG(std::cerr << "Constructing Kernel\n");
1117     success = schedule.constructKernel(II);
1118     if(!success) {
1119       ++II;
1120       schedule.clear();
1121     }
1122   }
1123 }
1124
1125
1126 bool ModuloSchedulingPass::scheduleNode(MSchedGraphNode *node,
1127                                       int start, int end) {
1128   bool success = false;
1129
1130   DEBUG(std::cerr << *node << " (Start Cycle: " << start << ", End Cycle: " << end << ")\n");
1131
1132   //Make sure start and end are not negative
1133   if(start < 0)
1134     start = 0;
1135   if(end < 0)
1136     end = 0;
1137
1138   bool forward = true;
1139   if(start > end)
1140     forward = false;
1141
1142   bool increaseSC = true;
1143   int cycle = start ;
1144
1145
1146   while(increaseSC) {
1147
1148     increaseSC = false;
1149
1150     increaseSC = schedule.insert(node, cycle);
1151
1152     if(!increaseSC)
1153       return true;
1154
1155     //Increment cycle to try again
1156     if(forward) {
1157       ++cycle;
1158       DEBUG(std::cerr << "Increase cycle: " << cycle << "\n");
1159       if(cycle > end)
1160         return false;
1161     }
1162     else {
1163       --cycle;
1164       DEBUG(std::cerr << "Decrease cycle: " << cycle << "\n");
1165       if(cycle < end)
1166         return false;
1167     }
1168   }
1169
1170   return success;
1171 }
1172
1173 void ModuloSchedulingPass::writePrologues(std::vector<MachineBasicBlock *> &prologues, MachineBasicBlock *origBB, std::vector<BasicBlock*> &llvm_prologues, std::map<const Value*, std::pair<const MSchedGraphNode*, int> > &valuesToSave, std::map<Value*, std::map<int, std::vector<Value*> > > &newValues, std::map<Value*, MachineBasicBlock*> &newValLocation) {
1174
1175   //Keep a map to easily know whats in the kernel
1176   std::map<int, std::set<const MachineInstr*> > inKernel;
1177   int maxStageCount = 0;
1178
1179   MSchedGraphNode *branch = 0;
1180
1181   for(MSSchedule::kernel_iterator I = schedule.kernel_begin(), E = schedule.kernel_end(); I != E; ++I) {
1182     maxStageCount = std::max(maxStageCount, I->second);
1183
1184     //Ignore the branch, we will handle this separately
1185     if(I->first->isBranch()) {
1186       branch = I->first;
1187       continue;
1188     }
1189
1190     //Put int the map so we know what instructions in each stage are in the kernel
1191     DEBUG(std::cerr << "Inserting instruction " << *(I->first->getInst()) << " into map at stage " << I->second << "\n");
1192     inKernel[I->second].insert(I->first->getInst());
1193   }
1194
1195   //Get target information to look at machine operands
1196   const TargetInstrInfo *mii = target.getInstrInfo();
1197
1198  //Now write the prologues
1199   for(int i = 0; i < maxStageCount; ++i) {
1200     BasicBlock *llvmBB = new BasicBlock("PROLOGUE", (Function*) (origBB->getBasicBlock()->getParent()));
1201     MachineBasicBlock *machineBB = new MachineBasicBlock(llvmBB);
1202
1203     DEBUG(std::cerr << "i=" << i << "\n");
1204     for(int j = 0; j <= i; ++j) {
1205       for(MachineBasicBlock::const_iterator MI = origBB->begin(), ME = origBB->end(); ME != MI; ++MI) {
1206         if(inKernel[j].count(&*MI)) {
1207           machineBB->push_back(MI->clone());
1208
1209           Instruction *tmp;
1210
1211           //After cloning, we may need to save the value that this instruction defines
1212           for(unsigned opNum=0; opNum < MI->getNumOperands(); ++opNum) {
1213             //get machine operand
1214             const MachineOperand &mOp = MI->getOperand(opNum);
1215             if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) {
1216
1217
1218               //Check if this is a value we should save
1219               if(valuesToSave.count(mOp.getVRegValue())) {
1220                 //Save copy in tmpInstruction
1221                 tmp = new TmpInstruction(mOp.getVRegValue());
1222
1223                 DEBUG(std::cerr << "Value: " << mOp.getVRegValue() << " New Value: " << tmp << " Stage: " << i << "\n");
1224                 newValues[mOp.getVRegValue()][i].push_back(tmp);
1225                 newValLocation[tmp] = machineBB;
1226
1227                 DEBUG(std::cerr << "Machine Instr Operands: " << mOp.getVRegValue() << ", 0, " << tmp << "\n");
1228
1229                 //Create machine instruction and put int machineBB
1230                 MachineInstr *saveValue = BuildMI(machineBB, V9::ORr, 3).addReg(mOp.getVRegValue()).addImm(0).addRegDef(tmp);
1231
1232                 DEBUG(std::cerr << "Created new machine instr: " << *saveValue << "\n");
1233               }
1234             }
1235           }
1236         }
1237       }
1238     }
1239
1240
1241     //Stick in branch at the end
1242     machineBB->push_back(branch->getInst()->clone());
1243
1244   (((MachineBasicBlock*)origBB)->getParent())->getBasicBlockList().push_back(machineBB);
1245     prologues.push_back(machineBB);
1246     llvm_prologues.push_back(llvmBB);
1247   }
1248 }
1249
1250 void ModuloSchedulingPass::writeEpilogues(std::vector<MachineBasicBlock *> &epilogues, const MachineBasicBlock *origBB, std::vector<BasicBlock*> &llvm_epilogues, std::map<const Value*, std::pair<const MSchedGraphNode*, int> > &valuesToSave, std::map<Value*, std::map<int, std::vector<Value*> > > &newValues,std::map<Value*, MachineBasicBlock*> &newValLocation ) {
1251
1252   std::map<int, std::set<const MachineInstr*> > inKernel;
1253   int maxStageCount = 0;
1254   for(MSSchedule::kernel_iterator I = schedule.kernel_begin(), E = schedule.kernel_end(); I != E; ++I) {
1255     maxStageCount = std::max(maxStageCount, I->second);
1256
1257     //Ignore the branch, we will handle this separately
1258     if(I->first->isBranch())
1259       continue;
1260
1261     //Put int the map so we know what instructions in each stage are in the kernel
1262     inKernel[I->second].insert(I->first->getInst());
1263   }
1264
1265   std::map<Value*, Value*> valPHIs;
1266
1267   //Now write the epilogues
1268   for(int i = maxStageCount-1; i >= 0; --i) {
1269     BasicBlock *llvmBB = new BasicBlock("EPILOGUE", (Function*) (origBB->getBasicBlock()->getParent()));
1270     MachineBasicBlock *machineBB = new MachineBasicBlock(llvmBB);
1271
1272     DEBUG(std::cerr << " i: " << i << "\n");
1273
1274     //Spit out phi nodes
1275     for(std::map<Value*, std::map<int, std::vector<Value*> > >::iterator V = newValues.begin(), E = newValues.end();
1276         V != E; ++V) {
1277
1278       DEBUG(std::cerr << "Writing phi for" << *(V->first));
1279       for(std::map<int, std::vector<Value*> >::iterator I = V->second.begin(), IE = V->second.end(); I != IE; ++I) {
1280         if(I->first == i) {
1281           DEBUG(std::cerr << "BLAH " << i << "\n");
1282
1283           //Vector must have two elements in it:
1284           assert(I->second.size() == 2 && "Vector size should be two\n");
1285
1286           Instruction *tmp = new TmpInstruction(I->second[0]);
1287           MachineInstr *saveValue = BuildMI(machineBB, V9::PHI, 3).addReg(I->second[0]).addReg(I->second[1]).addRegDef(tmp);
1288           valPHIs[V->first] = tmp;
1289         }
1290       }
1291
1292     }
1293
1294     for(MachineBasicBlock::const_iterator MI = origBB->begin(), ME = origBB->end(); ME != MI; ++MI) {
1295       for(int j=maxStageCount; j > i; --j) {
1296         if(inKernel[j].count(&*MI)) {
1297           DEBUG(std::cerr << "Cloning instruction " << *MI << "\n");
1298           MachineInstr *clone = MI->clone();
1299
1300           //Update operands that need to use the result from the phi
1301           for(unsigned i=0; i < clone->getNumOperands(); ++i) {
1302             //get machine operand
1303             const MachineOperand &mOp = clone->getOperand(i);
1304             if((mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isUse())) {
1305               if(valPHIs.count(mOp.getVRegValue())) {
1306                 //Update the operand in the cloned instruction
1307                 clone->getOperand(i).setValueReg(valPHIs[mOp.getVRegValue()]);
1308               }
1309             }
1310           }
1311           machineBB->push_back(clone);
1312         }
1313       }
1314     }
1315
1316     (((MachineBasicBlock*)origBB)->getParent())->getBasicBlockList().push_back(machineBB);
1317     epilogues.push_back(machineBB);
1318     llvm_epilogues.push_back(llvmBB);
1319   }
1320 }
1321
1322 void ModuloSchedulingPass::writeKernel(BasicBlock *llvmBB, MachineBasicBlock *machineBB, std::map<const Value*, std::pair<const MSchedGraphNode*, int> > &valuesToSave, std::map<Value*, std::map<int, std::vector<Value*> > > &newValues, std::map<Value*, MachineBasicBlock*> &newValLocation) {
1323
1324   //Keep track of operands that are read and saved from a previous iteration. The new clone
1325   //instruction will use the result of the phi instead.
1326   std::map<Value*, Value*> finalPHIValue;
1327   std::map<Value*, Value*> kernelValue;
1328
1329     //Create TmpInstructions for the final phis
1330  for(MSSchedule::kernel_iterator I = schedule.kernel_begin(), E = schedule.kernel_end(); I != E; ++I) {
1331
1332    //Clone instruction
1333    const MachineInstr *inst = I->first->getInst();
1334    MachineInstr *instClone = inst->clone();
1335
1336    //If this instruction is from a previous iteration, update its operands
1337    if(I->second > 0) {
1338      //Loop over Machine Operands
1339      const MachineInstr *inst = I->first->getInst();
1340      for(unsigned i=0; i < inst->getNumOperands(); ++i) {
1341        //get machine operand
1342        const MachineOperand &mOp = inst->getOperand(i);
1343
1344        if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isUse()) {
1345          //If its in the value saved, we need to create a temp instruction and use that instead
1346          if(valuesToSave.count(mOp.getVRegValue())) {
1347            TmpInstruction *tmp = new TmpInstruction(mOp.getVRegValue());
1348
1349            //Update the operand in the cloned instruction
1350            instClone->getOperand(i).setValueReg(tmp);
1351
1352            //save this as our final phi
1353            finalPHIValue[mOp.getVRegValue()] = tmp;
1354            newValLocation[tmp] = machineBB;
1355          }
1356        }
1357
1358      }
1359      //Insert into machine basic block
1360      machineBB->push_back(instClone);
1361
1362    }
1363    //Otherwise we just check if we need to save a value or not
1364    else {
1365      //Insert into machine basic block
1366      machineBB->push_back(instClone);
1367
1368      //Loop over Machine Operands
1369      const MachineInstr *inst = I->first->getInst();
1370      for(unsigned i=0; i < inst->getNumOperands(); ++i) {
1371        //get machine operand
1372        const MachineOperand &mOp = inst->getOperand(i);
1373
1374        if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) {
1375          if(valuesToSave.count(mOp.getVRegValue())) {
1376
1377            TmpInstruction *tmp = new TmpInstruction(mOp.getVRegValue());
1378
1379            //Create new machine instr and put in MBB
1380            MachineInstr *saveValue = BuildMI(machineBB, V9::ORr, 3).addReg(mOp.getVRegValue()).addImm(0).addRegDef(tmp);
1381
1382            //Save for future cleanup
1383            kernelValue[mOp.getVRegValue()] = tmp;
1384            newValLocation[tmp] = machineBB;
1385          }
1386        }
1387      }
1388    }
1389  }
1390
1391  //Clean up by writing phis
1392  for(std::map<Value*, std::map<int, std::vector<Value*> > >::iterator V = newValues.begin(), E = newValues.end();
1393      V != E; ++V) {
1394
1395    DEBUG(std::cerr << "Writing phi for" << *(V->first));
1396
1397    //FIXME
1398    int maxStage = 1;
1399
1400    //Last phi
1401    Instruction *lastPHI = 0;
1402
1403    for(std::map<int, std::vector<Value*> >::iterator I = V->second.begin(), IE = V->second.end();
1404        I != IE; ++I) {
1405
1406      int stage = I->first;
1407
1408      DEBUG(std::cerr << "Stage: " << I->first << " vector size: " << I->second.size() << "\n");
1409
1410      //Assert if this vector is ever greater then 1. This should not happen
1411      //FIXME: Get rid of vector if we convince ourselves this won't happn
1412      assert(I->second.size() == 1 && "Vector of values should be of size \n");
1413
1414      //We must handle the first and last phi specially
1415      if(stage == maxStage) {
1416        //The resulting value must be the Value* we created earlier
1417        assert(lastPHI != 0 && "Last phi is NULL!\n");
1418        MachineInstr *saveValue = BuildMI(*machineBB, machineBB->begin(), V9::PHI, 3).addReg(lastPHI).addReg(I->second[0]).addRegDef(finalPHIValue[V->first]);
1419        I->second.push_back(finalPHIValue[V->first]);
1420      }
1421      else if(stage == 0) {
1422        lastPHI = new TmpInstruction(I->second[0]);
1423        MachineInstr *saveValue = BuildMI(*machineBB, machineBB->begin(), V9::PHI, 3).addReg(kernelValue[V->first]).addReg(I->second[0]).addRegDef(lastPHI);
1424        I->second.push_back(lastPHI);
1425        newValLocation[lastPHI] = machineBB;
1426      }
1427      else {
1428         Instruction *tmp = new TmpInstruction(I->second[0]);
1429         MachineInstr *saveValue = BuildMI(*machineBB, machineBB->begin(), V9::PHI, 3).addReg(lastPHI).addReg(I->second[0]).addRegDef(tmp);
1430         lastPHI = tmp;
1431         I->second.push_back(lastPHI);
1432        newValLocation[tmp] = machineBB;
1433      }
1434    }
1435  }
1436 }
1437
1438 void ModuloSchedulingPass::removePHIs(const MachineBasicBlock *origBB, std::vector<MachineBasicBlock *> &prologues, std::vector<MachineBasicBlock *> &epilogues, MachineBasicBlock *kernelBB, std::map<Value*, MachineBasicBlock*> &newValLocation) {
1439
1440   //Worklist to delete things
1441   std::vector<std::pair<MachineBasicBlock*, MachineBasicBlock::iterator> > worklist;
1442
1443   const TargetInstrInfo *TMI = target.getInstrInfo();
1444
1445   //Start with the kernel and for each phi insert a copy for the phi def and for each arg
1446   for(MachineBasicBlock::iterator I = kernelBB->begin(), E = kernelBB->end(); I != E; ++I) {
1447     //Get op code and check if its a phi
1448      MachineOpCode OC = I->getOpcode();
1449      if(TMI->isDummyPhiInstr(OC)) {
1450        Instruction *tmp = 0;
1451        for(unsigned i = 0; i < I->getNumOperands(); ++i) {
1452          //Get Operand
1453          const MachineOperand &mOp = I->getOperand(i);
1454          assert(mOp.getType() == MachineOperand::MO_VirtualRegister && "Should be a Value*\n");
1455
1456          if(!tmp) {
1457            tmp = new TmpInstruction(mOp.getVRegValue());
1458          }
1459
1460          //Now for all our arguments we read, OR to the new TmpInstruction that we created
1461          if(mOp.isUse()) {
1462            DEBUG(std::cerr << "Use: " << mOp << "\n");
1463            //Place a copy at the end of its BB but before the branches
1464            assert(newValLocation.count(mOp.getVRegValue()) && "We must know where this value is located\n");
1465            //Reverse iterate to find the branches, we can safely assume no instructions have been
1466            //put in the nop positions
1467            for(MachineBasicBlock::iterator inst = --(newValLocation[mOp.getVRegValue()])->end(), endBB = (newValLocation[mOp.getVRegValue()])->begin(); inst != endBB; --inst) {
1468              MachineOpCode opc = inst->getOpcode();
1469              if(TMI->isBranch(opc) || TMI->isNop(opc))
1470                continue;
1471              else {
1472                BuildMI(*(newValLocation[mOp.getVRegValue()]), ++inst, V9::ORr, 3).addReg(mOp.getVRegValue()).addImm(0).addRegDef(tmp);
1473                break;
1474              }
1475
1476            }
1477
1478          }
1479          else {
1480            //Remove the phi and replace it with an OR
1481            DEBUG(std::cerr << "Def: " << mOp << "\n");
1482            BuildMI(*kernelBB, I, V9::ORr, 3).addReg(tmp).addImm(0).addRegDef(mOp.getVRegValue());
1483            worklist.push_back(std::make_pair(kernelBB, I));
1484          }
1485
1486        }
1487      }
1488
1489   }
1490
1491   //Remove phis from epilogue
1492   for(std::vector<MachineBasicBlock*>::iterator MB = epilogues.begin(), ME = epilogues.end(); MB != ME; ++MB) {
1493     for(MachineBasicBlock::iterator I = (*MB)->begin(), E = (*MB)->end(); I != E; ++I) {
1494       //Get op code and check if its a phi
1495       MachineOpCode OC = I->getOpcode();
1496       if(TMI->isDummyPhiInstr(OC)) {
1497         Instruction *tmp = 0;
1498         for(unsigned i = 0; i < I->getNumOperands(); ++i) {
1499           //Get Operand
1500           const MachineOperand &mOp = I->getOperand(i);
1501           assert(mOp.getType() == MachineOperand::MO_VirtualRegister && "Should be a Value*\n");
1502
1503           if(!tmp) {
1504             tmp = new TmpInstruction(mOp.getVRegValue());
1505           }
1506
1507           //Now for all our arguments we read, OR to the new TmpInstruction that we created
1508           if(mOp.isUse()) {
1509             DEBUG(std::cerr << "Use: " << mOp << "\n");
1510             //Place a copy at the end of its BB but before the branches
1511             assert(newValLocation.count(mOp.getVRegValue()) && "We must know where this value is located\n");
1512             //Reverse iterate to find the branches, we can safely assume no instructions have been
1513             //put in the nop positions
1514             for(MachineBasicBlock::iterator inst = --(newValLocation[mOp.getVRegValue()])->end(), endBB = (newValLocation[mOp.getVRegValue()])->begin(); inst != endBB; --inst) {
1515               MachineOpCode opc = inst->getOpcode();
1516               if(TMI->isBranch(opc) || TMI->isNop(opc))
1517                 continue;
1518               else {
1519                 BuildMI(*(newValLocation[mOp.getVRegValue()]), ++inst, V9::ORr, 3).addReg(mOp.getVRegValue()).addImm(0).addRegDef(tmp);
1520                 break;
1521               }
1522
1523             }
1524
1525           }
1526           else {
1527             //Remove the phi and replace it with an OR
1528             DEBUG(std::cerr << "Def: " << mOp << "\n");
1529             BuildMI(**MB, I, V9::ORr, 3).addReg(tmp).addImm(0).addRegDef(mOp.getVRegValue());
1530             worklist.push_back(std::make_pair(*MB,I));
1531           }
1532
1533         }
1534       }
1535     }
1536   }
1537
1538     //Delete the phis
1539   for(std::vector<std::pair<MachineBasicBlock*, MachineBasicBlock::iterator> >::iterator I =  worklist.begin(), E = worklist.end(); I != E; ++I) {
1540     I->first->erase(I->second);
1541
1542   }
1543
1544 }
1545
1546
1547 void ModuloSchedulingPass::reconstructLoop(MachineBasicBlock *BB) {
1548
1549   //First find the value *'s that we need to "save"
1550   std::map<const Value*, std::pair<const MSchedGraphNode*, int> > valuesToSave;
1551
1552   //Loop over kernel and only look at instructions from a stage > 0
1553   //Look at its operands and save values *'s that are read
1554   for(MSSchedule::kernel_iterator I = schedule.kernel_begin(), E = schedule.kernel_end(); I != E; ++I) {
1555
1556     if(I->second > 0) {
1557       //For this instruction, get the Value*'s that it reads and put them into the set.
1558       //Assert if there is an operand of another type that we need to save
1559       const MachineInstr *inst = I->first->getInst();
1560       for(unsigned i=0; i < inst->getNumOperands(); ++i) {
1561         //get machine operand
1562         const MachineOperand &mOp = inst->getOperand(i);
1563
1564         if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isUse()) {
1565           //find the value in the map
1566           if (const Value* srcI = mOp.getVRegValue())
1567             valuesToSave[srcI] = std::make_pair(I->first, i);
1568
1569         }
1570
1571         if(mOp.getType() != MachineOperand::MO_VirtualRegister && mOp.isUse()) {
1572           assert("Our assumption is wrong. We have another type of register that needs to be saved\n");
1573         }
1574       }
1575     }
1576   }
1577
1578   //The new loop will consist of one or more prologues, the kernel, and one or more epilogues.
1579
1580   //Map to keep track of old to new values
1581   std::map<Value*, std::map<int, std::vector<Value*> > > newValues;
1582
1583   //Another map to keep track of what machine basic blocks these new value*s are in since
1584   //they have no llvm instruction equivalent
1585   std::map<Value*, MachineBasicBlock*> newValLocation;
1586
1587   std::vector<MachineBasicBlock*> prologues;
1588   std::vector<BasicBlock*> llvm_prologues;
1589
1590
1591   //Write prologue
1592   writePrologues(prologues, BB, llvm_prologues, valuesToSave, newValues, newValLocation);
1593
1594   BasicBlock *llvmKernelBB = new BasicBlock("Kernel", (Function*) (BB->getBasicBlock()->getParent()));
1595   MachineBasicBlock *machineKernelBB = new MachineBasicBlock(llvmKernelBB);
1596
1597   writeKernel(llvmKernelBB, machineKernelBB, valuesToSave, newValues, newValLocation);
1598   (((MachineBasicBlock*)BB)->getParent())->getBasicBlockList().push_back(machineKernelBB);
1599
1600   std::vector<MachineBasicBlock*> epilogues;
1601   std::vector<BasicBlock*> llvm_epilogues;
1602
1603   //Write epilogues
1604   writeEpilogues(epilogues, BB, llvm_epilogues, valuesToSave, newValues, newValLocation);
1605
1606
1607   const TargetInstrInfo *TMI = target.getInstrInfo();
1608
1609   //Fix up machineBB and llvmBB branches
1610   for(unsigned I = 0; I <  prologues.size(); ++I) {
1611
1612     MachineInstr *branch = 0;
1613
1614     //Find terminator since getFirstTerminator does not work!
1615     for(MachineBasicBlock::reverse_iterator mInst = prologues[I]->rbegin(), mInstEnd = prologues[I]->rend(); mInst != mInstEnd; ++mInst) {
1616       MachineOpCode OC = mInst->getOpcode();
1617       if(TMI->isBranch(OC)) {
1618         branch = &*mInst;
1619         DEBUG(std::cerr << *mInst << "\n");
1620         break;
1621       }
1622     }
1623
1624
1625
1626     //Update branch
1627     for(unsigned opNum = 0; opNum < branch->getNumOperands(); ++opNum) {
1628       MachineOperand &mOp = branch->getOperand(opNum);
1629       if (mOp.getType() == MachineOperand::MO_PCRelativeDisp) {
1630         mOp.setValueReg(llvm_epilogues[(llvm_epilogues.size()-1-I)]);
1631       }
1632     }
1633
1634     //Update llvm basic block with our new branch instr
1635     DEBUG(std::cerr << BB->getBasicBlock()->getTerminator() << "\n");
1636     const BranchInst *branchVal = dyn_cast<BranchInst>(BB->getBasicBlock()->getTerminator());
1637     TmpInstruction *tmp = new TmpInstruction(branchVal->getCondition());
1638     if(I == prologues.size()-1) {
1639       TerminatorInst *newBranch = new BranchInst(llvmKernelBB,
1640                                                  llvm_epilogues[(llvm_epilogues.size()-1-I)],
1641                                                  tmp,
1642                                                  llvm_prologues[I]);
1643     }
1644     else
1645       TerminatorInst *newBranch = new BranchInst(llvm_prologues[I+1],
1646                                                  llvm_epilogues[(llvm_epilogues.size()-1-I)],
1647                                                  tmp,
1648                                                  llvm_prologues[I]);
1649
1650     assert(branch != 0 && "There must be a terminator for this machine basic block!\n");
1651
1652     //Push nop onto end of machine basic block
1653     BuildMI(prologues[I], V9::NOP, 0);
1654
1655     //Now since I don't trust fall throughs, add a unconditional branch to the next prologue
1656     if(I != prologues.size()-1)
1657       BuildMI(prologues[I], V9::BA, 1).addReg(llvm_prologues[I+1]);
1658     else
1659       BuildMI(prologues[I], V9::BA, 1).addReg(llvmKernelBB);
1660
1661     //Add one more nop!
1662     BuildMI(prologues[I], V9::NOP, 0);
1663   }
1664
1665   //Fix up kernel machine branches
1666   MachineInstr *branch = 0;
1667   for(MachineBasicBlock::reverse_iterator mInst = machineKernelBB->rbegin(), mInstEnd = machineKernelBB->rend(); mInst != mInstEnd; ++mInst) {
1668     MachineOpCode OC = mInst->getOpcode();
1669     if(TMI->isBranch(OC)) {
1670       branch = &*mInst;
1671       DEBUG(std::cerr << *mInst << "\n");
1672       break;
1673     }
1674   }
1675
1676   assert(branch != 0 && "There must be a terminator for the kernel machine basic block!\n");
1677
1678   //Update kernel self loop branch
1679   for(unsigned opNum = 0; opNum < branch->getNumOperands(); ++opNum) {
1680     MachineOperand &mOp = branch->getOperand(opNum);
1681
1682     if (mOp.getType() == MachineOperand::MO_PCRelativeDisp) {
1683       mOp.setValueReg(llvmKernelBB);
1684     }
1685   }
1686
1687   //Update kernelLLVM branches
1688   const BranchInst *branchVal = dyn_cast<BranchInst>(BB->getBasicBlock()->getTerminator());
1689   TerminatorInst *newBranch = new BranchInst(llvmKernelBB,
1690                                              llvm_epilogues[0],
1691                                              new TmpInstruction(branchVal->getCondition()),
1692                                              llvmKernelBB);
1693
1694   //Add kernel noop
1695    BuildMI(machineKernelBB, V9::NOP, 0);
1696
1697    //Add unconditional branch to first epilogue
1698    BuildMI(machineKernelBB, V9::BA, 1).addReg(llvm_epilogues[0]);
1699
1700    //Add kernel noop
1701    BuildMI(machineKernelBB, V9::NOP, 0);
1702
1703    //Lastly add unconditional branches for the epilogues
1704    for(unsigned I = 0; I <  epilogues.size(); ++I) {
1705
1706     //Now since I don't trust fall throughs, add a unconditional branch to the next prologue
1707      if(I != epilogues.size()-1) {
1708        BuildMI(epilogues[I], V9::BA, 1).addReg(llvm_epilogues[I+1]);
1709        //Add unconditional branch to end of epilogue
1710        TerminatorInst *newBranch = new BranchInst(llvm_epilogues[I+1],
1711                                                   llvm_epilogues[I]);
1712
1713      }
1714     else {
1715       MachineBasicBlock *origBlock = (MachineBasicBlock*) BB;
1716       for(MachineBasicBlock::reverse_iterator inst = origBlock->rbegin(), instEnd = origBlock->rend(); inst != instEnd; ++inst) {
1717         MachineOpCode OC = inst->getOpcode();
1718         if(TMI->isBranch(OC)) {
1719           branch = &*inst;
1720           DEBUG(std::cerr << *inst << "\n");
1721           break;
1722
1723         }
1724
1725         for(unsigned opNum = 0; opNum < branch->getNumOperands(); ++opNum) {
1726           MachineOperand &mOp = branch->getOperand(opNum);
1727
1728           if (mOp.getType() == MachineOperand::MO_PCRelativeDisp) {
1729             BuildMI(epilogues[I], V9::BA, 1).addReg(mOp.getVRegValue());
1730             break;
1731           }
1732         }
1733
1734       }
1735
1736       //Update last epilogue exit branch
1737       BranchInst *branchVal = (BranchInst*) dyn_cast<BranchInst>(BB->getBasicBlock()->getTerminator());
1738       //Find where we are supposed to branch to
1739       BasicBlock *nextBlock;
1740       for(unsigned j=0; j <branchVal->getNumSuccessors(); ++j) {
1741         if(branchVal->getSuccessor(j) != BB->getBasicBlock())
1742           nextBlock = branchVal->getSuccessor(j);
1743       }
1744         TerminatorInst *newBranch = new BranchInst(nextBlock, llvm_epilogues[I]);
1745     }
1746     //Add one more nop!
1747     BuildMI(epilogues[I], V9::NOP, 0);
1748
1749    }
1750
1751    //FIX UP Machine BB entry!!
1752    //We are looking at the predecesor of our loop basic block and we want to change its ba instruction
1753
1754
1755    //Find all llvm basic blocks that branch to the loop entry and change to our first prologue.
1756    const BasicBlock *llvmBB = BB->getBasicBlock();
1757
1758    for(pred_const_iterator P = pred_begin(llvmBB), PE = pred_end(llvmBB); P != PE; ++PE) {
1759      if(*P == llvmBB)
1760        continue;
1761      else {
1762        DEBUG(std::cerr << "Found our entry BB\n");
1763        //Get the Terminator instruction for this basic block and print it out
1764        DEBUG(std::cerr << *((*P)->getTerminator()) << "\n");
1765        //Update the terminator
1766        TerminatorInst *term = ((BasicBlock*)*P)->getTerminator();
1767        for(unsigned i=0; i < term->getNumSuccessors(); ++i) {
1768          if(term->getSuccessor(i) == llvmBB) {
1769            DEBUG(std::cerr << "Replacing successor bb\n");
1770            if(llvm_prologues.size() > 0) {
1771              term->setSuccessor(i, llvm_prologues[0]);
1772              //Also update its corresponding machine instruction
1773              MachineCodeForInstruction & tempMvec =
1774                MachineCodeForInstruction::get(term);
1775              for (unsigned j = 0; j < tempMvec.size(); j++) {
1776                MachineInstr *temp = tempMvec[j];
1777                MachineOpCode opc = temp->getOpcode();
1778                if(TMI->isBranch(opc)) {
1779                  DEBUG(std::cerr << *temp << "\n");
1780                  //Update branch
1781                  for(unsigned opNum = 0; opNum < temp->getNumOperands(); ++opNum) {
1782                    MachineOperand &mOp = temp->getOperand(opNum);
1783                    if (mOp.getType() == MachineOperand::MO_PCRelativeDisp) {
1784                      mOp.setValueReg(llvm_prologues[0]);
1785                    }
1786                  }
1787                }
1788              }
1789            }
1790            else {
1791              term->setSuccessor(i, llvmKernelBB);
1792            //Also update its corresponding machine instruction
1793              MachineCodeForInstruction & tempMvec =
1794                MachineCodeForInstruction::get(term);
1795              for (unsigned j = 0; j < tempMvec.size(); j++) {
1796                MachineInstr *temp = tempMvec[j];
1797                MachineOpCode opc = temp->getOpcode();
1798                if(TMI->isBranch(opc)) {
1799                  DEBUG(std::cerr << *temp << "\n");
1800                  //Update branch
1801                  for(unsigned opNum = 0; opNum < temp->getNumOperands(); ++opNum) {
1802                    MachineOperand &mOp = temp->getOperand(opNum);
1803                    if (mOp.getType() == MachineOperand::MO_PCRelativeDisp) {
1804                      mOp.setValueReg(llvmKernelBB);
1805                    }
1806                  }
1807                }
1808              }
1809            }
1810          }
1811        }
1812        break;
1813      }
1814    }
1815
1816    removePHIs(BB, prologues, epilogues, machineKernelBB, newValLocation);
1817
1818
1819
1820   //Print out epilogues and prologue
1821   DEBUG(for(std::vector<MachineBasicBlock*>::iterator I = prologues.begin(), E = prologues.end();
1822       I != E; ++I) {
1823     std::cerr << "PROLOGUE\n";
1824     (*I)->print(std::cerr);
1825   });
1826
1827   DEBUG(std::cerr << "KERNEL\n");
1828   DEBUG(machineKernelBB->print(std::cerr));
1829
1830   DEBUG(for(std::vector<MachineBasicBlock*>::iterator I = epilogues.begin(), E = epilogues.end();
1831       I != E; ++I) {
1832     std::cerr << "EPILOGUE\n";
1833     (*I)->print(std::cerr);
1834   });
1835
1836
1837   DEBUG(std::cerr << "New Machine Function" << "\n");
1838   DEBUG(std::cerr << BB->getParent() << "\n");
1839
1840   BB->getParent()->getBasicBlockList().erase(BB);
1841
1842 }
1843