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