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 //
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "ModuloSched"
  15
  16 #include "ModuloScheduling.h"
  17 #include "llvm/CodeGen/MachineFunction.h"
  18 #include "llvm/CodeGen/Passes.h"
  19 #include "llvm/Support/CFG.h"
  20 #include "llvm/Target/TargetSchedInfo.h"
  21 #include "Support/Debug.h"
  22 #include "Support/GraphWriter.h"
  23 #include "Support/StringExtras.h"
  24 #include <vector>
  25 #include <utility>
  26 #include <iostream>
  27 #include <fstream>
  28 #include <sstream>
  29
  30
  31 using namespace llvm;
  32
  33 /// Create ModuloSchedulingPass
  34 ///
  35 FunctionPass *llvm::createModuloSchedulingPass(TargetMachine & targ) {
  36   DEBUG(std::cerr << "Created ModuloSchedulingPass\n");
  37   return new ModuloSchedulingPass(targ);
  38 }
  39
  40 template<typename GraphType>
  41 static void WriteGraphToFile(std::ostream &O, const std::string &GraphName,
  42                              const GraphType &GT) {
  43   std::string Filename = GraphName + ".dot";
  44   O << "Writing '" << Filename << "'...";
  45   std::ofstream F(Filename.c_str());
  46
  47   if (F.good())
  48     WriteGraph(F, GT);
  49   else
  50     O << "  error opening file for writing!";
  51   O << "\n";
  52 };
  53
  54 namespace llvm {
  55
  56   template<>
  57   struct DOTGraphTraits<MSchedGraph*> : public DefaultDOTGraphTraits {
  58     static std::string getGraphName(MSchedGraph *F) {
  59       return "Dependence Graph";
  60     }
  61
  62     static std::string getNodeLabel(MSchedGraphNode *Node, MSchedGraph *Graph) {
  63       if (Node->getInst()) {
  64         std::stringstream ss;
  65         ss << *(Node->getInst());
  66         return ss.str(); //((MachineInstr*)Node->getInst());
  67       }
  68       else
  69         return "No Inst";
  70     }
  71     static std::string getEdgeSourceLabel(MSchedGraphNode *Node,
  72                                           MSchedGraphNode::succ_iterator I) {
  73       //Label each edge with the type of dependence
  74       std::string edgelabel = "";
  75       switch (I.getEdge().getDepOrderType()) {
  76
  77       case MSchedGraphEdge::TrueDep:
  78         edgelabel = "True";
  79         break;
  80
  81       case MSchedGraphEdge::AntiDep:
  82         edgelabel =  "Anti";
  83         break;
  84
  85       case MSchedGraphEdge::OutputDep:
  86         edgelabel = "Output";
  87         break;
  88
  89       default:
  90         edgelabel = "Unknown";
  91         break;
  92       }
  93
  94       //FIXME
  95       int iteDiff = I.getEdge().getIteDiff();
  96       std::string intStr = "(IteDiff: ";
  97       intStr += itostr(iteDiff);
  98
  99       intStr += ")";
 100       edgelabel += intStr;
 101
 102       return edgelabel;
 103     }
 104
 105
 106
 107   };
 108 }
 109
 110 /// ModuloScheduling::runOnFunction - main transformation entry point
 111 bool ModuloSchedulingPass::runOnFunction(Function &F) {
 112   bool Changed = false;
 113
 114   DEBUG(std::cerr << "Creating ModuloSchedGraph for each BasicBlock in" + F.getName() + "\n");
 115
 116   //Get MachineFunction
 117   MachineFunction &MF = MachineFunction::get(&F);
 118
 119   //Iterate over BasicBlocks and do ModuloScheduling if they are valid
 120   for (MachineFunction::const_iterator BI = MF.begin(); BI != MF.end(); ++BI) {
 121     if(MachineBBisValid(BI)) {
 122       MSchedGraph *MSG = new MSchedGraph(BI, target);
 123
 124       //Write Graph out to file
 125       DEBUG(WriteGraphToFile(std::cerr, F.getName(), MSG));
 126
 127       //Print out BB for debugging
 128       DEBUG(BI->print(std::cerr));
 129
 130       //Calculate Resource II
 131       int ResMII = calculateResMII(BI);
 132
 133       //Calculate Recurrence II
 134       int RecMII = calculateRecMII(MSG, ResMII);
 135
 136       II = std::max(RecMII, ResMII);
 137
 138
 139       DEBUG(std::cerr << "II starts out as " << II << " ( RecMII=" << RecMII << "and ResMII=" << ResMII << "\n");
 140
 141       //Calculate Node Properties
 142       calculateNodeAttributes(MSG, ResMII);
 143
 144       //Dump node properties if in debug mode
 145       for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I =  nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I !=E; ++I) {
 146         DEBUG(std::cerr << "Node: " << *(I->first) << " ASAP: " << I->second.ASAP << " ALAP: " << I->second.ALAP << " MOB: " << I->second.MOB << " Depth: " << I->second.depth << " Height: " << I->second.height << "\n");
 147       }
 148
 149       //Put nodes in order to schedule them
 150       computePartialOrder();
 151
 152       //Dump out partial order
 153       for(std::vector<std::vector<MSchedGraphNode*> >::iterator I = partialOrder.begin(), E = partialOrder.end(); I !=E; ++I) {
 154         DEBUG(std::cerr << "Start set in PO\n");
 155         for(std::vector<MSchedGraphNode*>::iterator J = I->begin(), JE = I->end(); J != JE; ++J)
 156           DEBUG(std::cerr << "PO:" << **J << "\n");
 157       }
 158
 159       orderNodes();
 160
 161       //Dump out order of nodes
 162       for(std::vector<MSchedGraphNode*>::iterator I = FinalNodeOrder.begin(), E = FinalNodeOrder.end(); I != E; ++I)
 163         DEBUG(std::cerr << "FO:" << **I << "\n");
 164
 165
 166       //Finally schedule nodes
 167       computeSchedule();
 168
 169       DEBUG(schedule.print(std::cerr));
 170
 171       reconstructLoop(BI);
 172
 173
 174       nodeToAttributesMap.clear();
 175       partialOrder.clear();
 176       recurrenceList.clear();
 177       FinalNodeOrder.clear();
 178       schedule.clear();
 179       }
 180
 181   }
 182
 183
 184   return Changed;
 185 }
 186
 187
 188 bool ModuloSchedulingPass::MachineBBisValid(const MachineBasicBlock *BI) {
 189
 190   //Valid basic blocks must be loops and can not have if/else statements or calls.
 191   bool isLoop = false;
 192
 193   //Check first if its a valid loop
 194   for(succ_const_iterator I = succ_begin(BI->getBasicBlock()),
 195         E = succ_end(BI->getBasicBlock()); I != E; ++I) {
 196     if (*I == BI->getBasicBlock())    // has single block loop
 197       isLoop = true;
 198   }
 199
 200   if(!isLoop) {
 201     DEBUG(std::cerr << "Basic Block is not a loop\n");
 202     return false;
 203   }
 204   else
 205     DEBUG(std::cerr << "Basic Block is a loop\n");
 206
 207   //Get Target machine instruction info
 208   /*const TargetInstrInfo& TMI = targ.getInstrInfo();
 209
 210   //Check each instruction and look for calls or if/else statements
 211   unsigned count = 0;
 212   for(MachineBasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I) {
 213   //Get opcode to check instruction type
 214   MachineOpCode OC = I->getOpcode();
 215   if(TMI.isControlFlow(OC) && (count+1 < BI->size()))
 216   return false;
 217   count++;
 218   }*/
 219   return true;
 220
 221 }
 222
 223 //ResMII is calculated by determining the usage count for each resource
 224 //and using the maximum.
 225 //FIXME: In future there should be a way to get alternative resources
 226 //for each instruction
 227 int ModuloSchedulingPass::calculateResMII(const MachineBasicBlock *BI) {
 228
 229   const TargetInstrInfo & mii = target.getInstrInfo();
 230   const TargetSchedInfo & msi = target.getSchedInfo();
 231
 232   int ResMII = 0;
 233
 234   //Map to keep track of usage count of each resource
 235   std::map<unsigned, unsigned> resourceUsageCount;
 236
 237   for(MachineBasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I) {
 238
 239     //Get resource usage for this instruction
 240     InstrRUsage rUsage = msi.getInstrRUsage(I->getOpcode());
 241     std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
 242
 243     //Loop over resources in each cycle and increments their usage count
 244     for(unsigned i=0; i < resources.size(); ++i)
 245       for(unsigned j=0; j < resources[i].size(); ++j) {
 246         if( resourceUsageCount.find(resources[i][j]) == resourceUsageCount.end()) {
 247           resourceUsageCount[resources[i][j]] = 1;
 248         }
 249         else {
 250           resourceUsageCount[resources[i][j]] =  resourceUsageCount[resources[i][j]] + 1;
 251         }
 252       }
 253   }
 254
 255   //Find maximum usage count
 256
 257   //Get max number of instructions that can be issued at once. (FIXME)
 258   int issueSlots = msi.maxNumIssueTotal;
 259
 260   for(std::map<unsigned,unsigned>::iterator RB = resourceUsageCount.begin(), RE = resourceUsageCount.end(); RB != RE; ++RB) {
 261
 262     //Get the total number of the resources in our cpu
 263     int resourceNum = CPUResource::getCPUResource(RB->first)->maxNumUsers;
 264
 265     //Get total usage count for this resources
 266     unsigned usageCount = RB->second;
 267
 268     //Divide the usage count by either the max number we can issue or the number of
 269     //resources (whichever is its upper bound)
 270     double finalUsageCount;
 271     if( resourceNum <= issueSlots)
 272       finalUsageCount = ceil(1.0 * usageCount / resourceNum);
 273     else
 274       finalUsageCount = ceil(1.0 * usageCount / issueSlots);
 275
 276
 277     DEBUG(std::cerr << "Resource ID: " << RB->first << " (usage=" << usageCount << ", resourceNum=X" << ", issueSlots=" << issueSlots << ", finalUsage=" << finalUsageCount << ")\n");
 278
 279     //Only keep track of the max
 280     ResMII = std::max( (int) finalUsageCount, ResMII);
 281
 282   }
 283
 284   DEBUG(std::cerr << "Final Resource MII: " << ResMII << "\n");
 285
 286   return ResMII;
 287
 288 }
 289
 290 int ModuloSchedulingPass::calculateRecMII(MSchedGraph *graph, int MII) {
 291   std::vector<MSchedGraphNode*> vNodes;
 292   //Loop over all nodes in the graph
 293   for(MSchedGraph::iterator I = graph->begin(), E = graph->end(); I != E; ++I) {
 294     findAllReccurrences(I->second, vNodes, MII);
 295     vNodes.clear();
 296   }
 297
 298   int RecMII = 0;
 299
 300   for(std::set<std::pair<int, std::vector<MSchedGraphNode*> > >::iterator I = recurrenceList.begin(), E=recurrenceList.end(); I !=E; ++I) {
 301     std::cerr << "Recurrence: \n";
 302     for(std::vector<MSchedGraphNode*>::const_iterator N = I->second.begin(), NE = I->second.end(); N != NE; ++N) {
 303       std::cerr << **N << "\n";
 304     }
 305     RecMII = std::max(RecMII, I->first);
 306     std::cerr << "End Recurrence with RecMII: " << I->first << "\n";
 307     }
 308   DEBUG(std::cerr << "RecMII: " << RecMII << "\n");
 309
 310   return MII;
 311 }
 312
 313 void ModuloSchedulingPass::calculateNodeAttributes(MSchedGraph *graph, int MII) {
 314
 315   //Loop over the nodes and add them to the map
 316   for(MSchedGraph::iterator I = graph->begin(), E = graph->end(); I != E; ++I) {
 317     //Assert if its already in the map
 318     assert(nodeToAttributesMap.find(I->second) == nodeToAttributesMap.end() && "Node attributes are already in the map");
 319
 320     //Put into the map with default attribute values
 321     nodeToAttributesMap[I->second] = MSNodeAttributes();
 322   }
 323
 324   //Create set to deal with reccurrences
 325   std::set<MSchedGraphNode*> visitedNodes;
 326
 327   //Now Loop over map and calculate the node attributes
 328   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
 329     calculateASAP(I->first, MII, (MSchedGraphNode*) 0);
 330     visitedNodes.clear();
 331   }
 332
 333   int maxASAP = findMaxASAP();
 334   //Calculate ALAP which depends on ASAP being totally calculated
 335   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
 336     calculateALAP(I->first, MII, maxASAP, (MSchedGraphNode*) 0);
 337     visitedNodes.clear();
 338   }
 339
 340   //Calculate MOB which depends on ASAP being totally calculated, also do depth and height
 341   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
 342     (I->second).MOB = std::max(0,(I->second).ALAP - (I->second).ASAP);
 343
 344     DEBUG(std::cerr << "MOB: " << (I->second).MOB << " (" << *(I->first) << ")\n");
 345     calculateDepth(I->first, (MSchedGraphNode*) 0);
 346     calculateHeight(I->first, (MSchedGraphNode*) 0);
 347   }
 348
 349
 350 }
 351
 352 bool ModuloSchedulingPass::ignoreEdge(MSchedGraphNode *srcNode, MSchedGraphNode *destNode) {
 353   if(destNode == 0 || srcNode ==0)
 354     return false;
 355
 356   bool findEdge = edgesToIgnore.count(std::make_pair(srcNode, destNode->getInEdgeNum(srcNode)));
 357
 358   return findEdge;
 359 }
 360
 361 int  ModuloSchedulingPass::calculateASAP(MSchedGraphNode *node, int MII, MSchedGraphNode *destNode) {
 362
 363   DEBUG(std::cerr << "Calculating ASAP for " << *node << "\n");
 364
 365   //Get current node attributes
 366   MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second;
 367
 368   if(attributes.ASAP != -1)
 369     return attributes.ASAP;
 370
 371   int maxPredValue = 0;
 372
 373   //Iterate over all of the predecessors and find max
 374   for(MSchedGraphNode::pred_iterator P = node->pred_begin(), E = node->pred_end(); P != E; ++P) {
 375
 376     //Only process if we are not ignoring the edge
 377     if(!ignoreEdge(*P, node)) {
 378       int predASAP = -1;
 379       predASAP = calculateASAP(*P, MII, node);
 380
 381       assert(predASAP != -1 && "ASAP has not been calculated");
 382       int iteDiff = node->getInEdge(*P).getIteDiff();
 383
 384       int currentPredValue = predASAP + (*P)->getLatency() - (iteDiff * MII);
 385       DEBUG(std::cerr << "pred ASAP: " << predASAP << ", iteDiff: " << iteDiff << ", PredLatency: " << (*P)->getLatency() << ", Current ASAP pred: " << currentPredValue << "\n");
 386       maxPredValue = std::max(maxPredValue, currentPredValue);
 387     }
 388   }
 389
 390   attributes.ASAP = maxPredValue;
 391
 392   DEBUG(std::cerr << "ASAP: " << attributes.ASAP << " (" << *node << ")\n");
 393
 394   return maxPredValue;
 395 }
 396
 397
 398 int ModuloSchedulingPass::calculateALAP(MSchedGraphNode *node, int MII,
 399                                         int maxASAP, MSchedGraphNode *srcNode) {
 400
 401   DEBUG(std::cerr << "Calculating ALAP for " << *node << "\n");
 402
 403   MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second;
 404
 405   if(attributes.ALAP != -1)
 406     return attributes.ALAP;
 407
 408   if(node->hasSuccessors()) {
 409
 410     //Trying to deal with the issue where the node has successors, but
 411     //we are ignoring all of the edges to them. So this is my hack for
 412     //now.. there is probably a more elegant way of doing this (FIXME)
 413     bool processedOneEdge = false;
 414
 415     //FIXME, set to something high to start
 416     int minSuccValue = 9999999;
 417
 418     //Iterate over all of the predecessors and fine max
 419     for(MSchedGraphNode::succ_iterator P = node->succ_begin(),
 420           E = node->succ_end(); P != E; ++P) {
 421
 422       //Only process if we are not ignoring the edge
 423       if(!ignoreEdge(node, *P)) {
 424         processedOneEdge = true;
 425         int succALAP = -1;
 426         succALAP = calculateALAP(*P, MII, maxASAP, node);
 427
 428         assert(succALAP != -1 && "Successors ALAP should have been caclulated");
 429
 430         int iteDiff = P.getEdge().getIteDiff();
 431
 432         int currentSuccValue = succALAP - node->getLatency() + iteDiff * MII;
 433
 434         DEBUG(std::cerr << "succ ALAP: " << succALAP << ", iteDiff: " << iteDiff << ", SuccLatency: " << (*P)->getLatency() << ", Current ALAP succ: " << currentSuccValue << "\n");
 435
 436         minSuccValue = std::min(minSuccValue, currentSuccValue);
 437       }
 438     }
 439
 440     if(processedOneEdge)
 441         attributes.ALAP = minSuccValue;
 442
 443     else
 444       attributes.ALAP = maxASAP;
 445   }
 446   else
 447     attributes.ALAP = maxASAP;
 448
 449   DEBUG(std::cerr << "ALAP: " << attributes.ALAP << " (" << *node << ")\n");
 450
 451   if(attributes.ALAP < 0)
 452     attributes.ALAP = 0;
 453
 454   return attributes.ALAP;
 455 }
 456
 457 int ModuloSchedulingPass::findMaxASAP() {
 458   int maxASAP = 0;
 459
 460   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(),
 461         E = nodeToAttributesMap.end(); I != E; ++I)
 462     maxASAP = std::max(maxASAP, I->second.ASAP);
 463   return maxASAP;
 464 }
 465
 466
 467 int ModuloSchedulingPass::calculateHeight(MSchedGraphNode *node,MSchedGraphNode *srcNode) {
 468
 469   MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second;
 470
 471   if(attributes.height != -1)
 472     return attributes.height;
 473
 474   int maxHeight = 0;
 475
 476   //Iterate over all of the predecessors and find max
 477   for(MSchedGraphNode::succ_iterator P = node->succ_begin(),
 478         E = node->succ_end(); P != E; ++P) {
 479
 480
 481     if(!ignoreEdge(node, *P)) {
 482       int succHeight = calculateHeight(*P, node);
 483
 484       assert(succHeight != -1 && "Successors Height should have been caclulated");
 485
 486       int currentHeight = succHeight + node->getLatency();
 487       maxHeight = std::max(maxHeight, currentHeight);
 488     }
 489   }
 490   attributes.height = maxHeight;
 491   DEBUG(std::cerr << "Height: " << attributes.height << " (" << *node << ")\n");
 492   return maxHeight;
 493 }
 494
 495
 496 int ModuloSchedulingPass::calculateDepth(MSchedGraphNode *node,
 497                                           MSchedGraphNode *destNode) {
 498
 499   MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second;
 500
 501   if(attributes.depth != -1)
 502     return attributes.depth;
 503
 504   int maxDepth = 0;
 505
 506   //Iterate over all of the predecessors and fine max
 507   for(MSchedGraphNode::pred_iterator P = node->pred_begin(), E = node->pred_end(); P != E; ++P) {
 508
 509     if(!ignoreEdge(*P, node)) {
 510       int predDepth = -1;
 511       predDepth = calculateDepth(*P, node);
 512
 513       assert(predDepth != -1 && "Predecessors ASAP should have been caclulated");
 514
 515       int currentDepth = predDepth + (*P)->getLatency();
 516       maxDepth = std::max(maxDepth, currentDepth);
 517     }
 518   }
 519   attributes.depth = maxDepth;
 520
 521   DEBUG(std::cerr << "Depth: " << attributes.depth << " (" << *node << "*)\n");
 522   return maxDepth;
 523 }
 524
 525
 526
 527 void ModuloSchedulingPass::addReccurrence(std::vector<MSchedGraphNode*> &recurrence, int II, MSchedGraphNode *srcBENode, MSchedGraphNode *destBENode) {
 528   //Check to make sure that this recurrence is unique
 529   bool same = false;
 530
 531
 532   //Loop over all recurrences already in our list
 533   for(std::set<std::pair<int, std::vector<MSchedGraphNode*> > >::iterator R = recurrenceList.begin(), RE = recurrenceList.end(); R != RE; ++R) {
 534
 535     bool all_same = true;
 536      //First compare size
 537     if(R->second.size() == recurrence.size()) {
 538
 539       for(std::vector<MSchedGraphNode*>::const_iterator node = R->second.begin(), end = R->second.end(); node != end; ++node) {
 540         if(find(recurrence.begin(), recurrence.end(), *node) == recurrence.end()) {
 541           all_same = all_same && false;
 542           break;
 543         }
 544         else
 545           all_same = all_same && true;
 546       }
 547       if(all_same) {
 548         same = true;
 549         break;
 550       }
 551     }
 552   }
 553
 554   if(!same) {
 555     srcBENode = recurrence.back();
 556     destBENode = recurrence.front();
 557
 558     //FIXME
 559     if(destBENode->getInEdge(srcBENode).getIteDiff() == 0) {
 560       //DEBUG(std::cerr << "NOT A BACKEDGE\n");
 561       //find actual backedge HACK HACK
 562       for(unsigned i=0; i< recurrence.size()-1; ++i) {
 563         if(recurrence[i+1]->getInEdge(recurrence[i]).getIteDiff() == 1) {
 564           srcBENode = recurrence[i];
 565           destBENode = recurrence[i+1];
 566           break;
 567         }
 568
 569       }
 570
 571     }
 572     DEBUG(std::cerr << "Back Edge to Remove: " << *srcBENode << " to " << *destBENode << "\n");
 573     edgesToIgnore.insert(std::make_pair(srcBENode, destBENode->getInEdgeNum(srcBENode)));
 574     recurrenceList.insert(std::make_pair(II, recurrence));
 575   }
 576
 577 }
 578
 579 void ModuloSchedulingPass::findAllReccurrences(MSchedGraphNode *node,
 580                                                std::vector<MSchedGraphNode*> &visitedNodes,
 581                                                int II) {
 582
 583   if(find(visitedNodes.begin(), visitedNodes.end(), node) != visitedNodes.end()) {
 584     std::vector<MSchedGraphNode*> recurrence;
 585     bool first = true;
 586     int delay = 0;
 587     int distance = 0;
 588     int RecMII = II; //Starting value
 589     MSchedGraphNode *last = node;
 590     MSchedGraphNode *srcBackEdge;
 591     MSchedGraphNode *destBackEdge;
 592
 593
 594
 595     for(std::vector<MSchedGraphNode*>::iterator I = visitedNodes.begin(), E = visitedNodes.end();
 596         I !=E; ++I) {
 597
 598       if(*I == node)
 599         first = false;
 600       if(first)
 601         continue;
 602
 603       delay = delay + (*I)->getLatency();
 604
 605       if(*I != node) {
 606         int diff = (*I)->getInEdge(last).getIteDiff();
 607         distance += diff;
 608         if(diff > 0) {
 609           srcBackEdge = last;
 610           destBackEdge = *I;
 611         }
 612       }
 613
 614       recurrence.push_back(*I);
 615       last = *I;
 616     }
 617
 618
 619
 620     //Get final distance calc
 621     distance += node->getInEdge(last).getIteDiff();
 622
 623
 624     //Adjust II until we get close to the inequality delay - II*distance <= 0
 625
 626     int value = delay-(RecMII * distance);
 627     int lastII = II;
 628     while(value <= 0) {
 629
 630       lastII = RecMII;
 631       RecMII--;
 632       value = delay-(RecMII * distance);
 633     }
 634
 635
 636     DEBUG(std::cerr << "Final II for this recurrence: " << lastII << "\n");
 637     addReccurrence(recurrence, lastII, srcBackEdge, destBackEdge);
 638     assert(distance != 0 && "Recurrence distance should not be zero");
 639     return;
 640   }
 641
 642   for(MSchedGraphNode::succ_iterator I = node->succ_begin(), E = node->succ_end(); I != E; ++I) {
 643     visitedNodes.push_back(node);
 644     findAllReccurrences(*I, visitedNodes, II);
 645     visitedNodes.pop_back();
 646   }
 647 }
 648
 649
 650
 651
 652
 653 void ModuloSchedulingPass::computePartialOrder() {
 654
 655
 656   //Loop over all recurrences and add to our partial order
 657   //be sure to remove nodes that are already in the partial order in
 658   //a different recurrence and don't add empty recurrences.
 659   for(std::set<std::pair<int, std::vector<MSchedGraphNode*> > >::reverse_iterator I = recurrenceList.rbegin(), E=recurrenceList.rend(); I !=E; ++I) {
 660
 661     //Add nodes that connect this recurrence to the previous recurrence
 662
 663     //If this is the first recurrence in the partial order, add all predecessors
 664     for(std::vector<MSchedGraphNode*>::const_iterator N = I->second.begin(), NE = I->second.end(); N != NE; ++N) {
 665
 666     }
 667
 668
 669     std::vector<MSchedGraphNode*> new_recurrence;
 670     //Loop through recurrence and remove any nodes already in the partial order
 671     for(std::vector<MSchedGraphNode*>::const_iterator N = I->second.begin(), NE = I->second.end(); N != NE; ++N) {
 672       bool found = false;
 673       for(std::vector<std::vector<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), PE = partialOrder.end(); PO != PE; ++PO) {
 674         if(find(PO->begin(), PO->end(), *N) != PO->end())
 675           found = true;
 676       }
 677       if(!found) {
 678         new_recurrence.push_back(*N);
 679
 680         if(partialOrder.size() == 0)
 681           //For each predecessors, add it to this recurrence ONLY if it is not already in it
 682           for(MSchedGraphNode::pred_iterator P = (*N)->pred_begin(),
 683                 PE = (*N)->pred_end(); P != PE; ++P) {
 684
 685             //Check if we are supposed to ignore this edge or not
 686             if(!ignoreEdge(*P, *N))
 687               //Check if already in this recurrence
 688               if(find(I->second.begin(), I->second.end(), *P) == I->second.end()) {
 689                 //Also need to check if in partial order
 690                 bool predFound = false;
 691                 for(std::vector<std::vector<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), PEND = partialOrder.end(); PO != PEND; ++PO) {
 692                   if(find(PO->begin(), PO->end(), *P) != PO->end())
 693                     predFound = true;
 694                 }
 695
 696                 if(!predFound)
 697                   if(find(new_recurrence.begin(), new_recurrence.end(), *P) == new_recurrence.end())
 698                      new_recurrence.push_back(*P);
 699
 700               }
 701           }
 702       }
 703     }
 704
 705
 706     if(new_recurrence.size() > 0)
 707       partialOrder.push_back(new_recurrence);
 708   }
 709
 710   //Add any nodes that are not already in the partial order
 711   std::vector<MSchedGraphNode*> lastNodes;
 712   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
 713     bool found = false;
 714     //Check if its already in our partial order, if not add it to the final vector
 715     for(std::vector<std::vector<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), PE = partialOrder.end(); PO != PE; ++PO) {
 716       if(find(PO->begin(), PO->end(), I->first) != PO->end())
 717         found = true;
 718     }
 719     if(!found)
 720       lastNodes.push_back(I->first);
 721   }
 722
 723   if(lastNodes.size() > 0)
 724     partialOrder.push_back(lastNodes);
 725
 726 }
 727
 728
 729 void ModuloSchedulingPass::predIntersect(std::vector<MSchedGraphNode*> &CurrentSet, std::vector<MSchedGraphNode*> &IntersectResult) {
 730
 731   //Sort CurrentSet so we can use lowerbound
 732   sort(CurrentSet.begin(), CurrentSet.end());
 733
 734   for(unsigned j=0; j < FinalNodeOrder.size(); ++j) {
 735     for(MSchedGraphNode::pred_iterator P = FinalNodeOrder[j]->pred_begin(),
 736           E = FinalNodeOrder[j]->pred_end(); P != E; ++P) {
 737
 738       //Check if we are supposed to ignore this edge or not
 739       if(ignoreEdge(*P,FinalNodeOrder[j]))
 740         continue;
 741
 742       if(find(CurrentSet.begin(),
 743                      CurrentSet.end(), *P) != CurrentSet.end())
 744         if(find(FinalNodeOrder.begin(), FinalNodeOrder.end(), *P) == FinalNodeOrder.end())
 745           IntersectResult.push_back(*P);
 746     }
 747   }
 748 }
 749
 750 void ModuloSchedulingPass::succIntersect(std::vector<MSchedGraphNode*> &CurrentSet, std::vector<MSchedGraphNode*> &IntersectResult) {
 751
 752   //Sort CurrentSet so we can use lowerbound
 753   sort(CurrentSet.begin(), CurrentSet.end());
 754
 755   for(unsigned j=0; j < FinalNodeOrder.size(); ++j) {
 756     for(MSchedGraphNode::succ_iterator P = FinalNodeOrder[j]->succ_begin(),
 757           E = FinalNodeOrder[j]->succ_end(); P != E; ++P) {
 758
 759       //Check if we are supposed to ignore this edge or not
 760       if(ignoreEdge(FinalNodeOrder[j],*P))
 761         continue;
 762
 763       if(find(CurrentSet.begin(),
 764                      CurrentSet.end(), *P) != CurrentSet.end())
 765         if(find(FinalNodeOrder.begin(), FinalNodeOrder.end(), *P) == FinalNodeOrder.end())
 766           IntersectResult.push_back(*P);
 767     }
 768   }
 769 }
 770
 771 void dumpIntersection(std::vector<MSchedGraphNode*> &IntersectCurrent) {
 772   std::cerr << "Intersection (";
 773   for(std::vector<MSchedGraphNode*>::iterator I = IntersectCurrent.begin(), E = IntersectCurrent.end(); I != E; ++I)
 774     std::cerr << **I << ", ";
 775   std::cerr << ")\n";
 776 }
 777
 778
 779
 780 void ModuloSchedulingPass::orderNodes() {
 781
 782   int BOTTOM_UP = 0;
 783   int TOP_DOWN = 1;
 784
 785   //Set default order
 786   int order = BOTTOM_UP;
 787
 788
 789   //Loop over all the sets and place them in the final node order
 790   for(std::vector<std::vector<MSchedGraphNode*> >::iterator CurrentSet = partialOrder.begin(), E= partialOrder.end(); CurrentSet != E; ++CurrentSet) {
 791
 792     DEBUG(std::cerr << "Processing set in S\n");
 793     dumpIntersection(*CurrentSet);
 794     //Result of intersection
 795     std::vector<MSchedGraphNode*> IntersectCurrent;
 796
 797     predIntersect(*CurrentSet, IntersectCurrent);
 798
 799     //If the intersection of predecessor and current set is not empty
 800     //sort nodes bottom up
 801     if(IntersectCurrent.size() != 0) {
 802       DEBUG(std::cerr << "Final Node Order Predecessors and Current Set interesection is NOT empty\n");
 803       order = BOTTOM_UP;
 804     }
 805     //If empty, use successors
 806     else {
 807       DEBUG(std::cerr << "Final Node Order Predecessors and Current Set interesection is empty\n");
 808
 809       succIntersect(*CurrentSet, IntersectCurrent);
 810
 811       //sort top-down
 812       if(IntersectCurrent.size() != 0) {
 813          DEBUG(std::cerr << "Final Node Order Successors and Current Set interesection is NOT empty\n");
 814         order = TOP_DOWN;
 815       }
 816       else {
 817         DEBUG(std::cerr << "Final Node Order Successors and Current Set interesection is empty\n");
 818         //Find node with max ASAP in current Set
 819         MSchedGraphNode *node;
 820         int maxASAP = 0;
 821         DEBUG(std::cerr << "Using current set of size " << CurrentSet->size() << "to find max ASAP\n");
 822         for(unsigned j=0; j < CurrentSet->size(); ++j) {
 823           //Get node attributes
 824           MSNodeAttributes nodeAttr= nodeToAttributesMap.find((*CurrentSet)[j])->second;
 825           //assert(nodeAttr != nodeToAttributesMap.end() && "Node not in attributes map!");
 826           DEBUG(std::cerr << "CurrentSet index " << j << "has ASAP: " << nodeAttr.ASAP << "\n");
 827           if(maxASAP < nodeAttr.ASAP) {
 828             maxASAP = nodeAttr.ASAP;
 829             node = (*CurrentSet)[j];
 830           }
 831         }
 832         assert(node != 0 && "In node ordering node should not be null");
 833         IntersectCurrent.push_back(node);
 834         order = BOTTOM_UP;
 835       }
 836     }
 837
 838     //Repeat until all nodes are put into the final order from current set
 839     while(IntersectCurrent.size() > 0) {
 840
 841       if(order == TOP_DOWN) {
 842         DEBUG(std::cerr << "Order is TOP DOWN\n");
 843
 844         while(IntersectCurrent.size() > 0) {
 845           DEBUG(std::cerr << "Intersection is not empty, so find heighest height\n");
 846
 847           int MOB = 0;
 848           int height = 0;
 849           MSchedGraphNode *highestHeightNode = IntersectCurrent[0];
 850
 851           //Find node in intersection with highest heigh and lowest MOB
 852           for(std::vector<MSchedGraphNode*>::iterator I = IntersectCurrent.begin(),
 853                 E = IntersectCurrent.end(); I != E; ++I) {
 854
 855             //Get current nodes properties
 856             MSNodeAttributes nodeAttr= nodeToAttributesMap.find(*I)->second;
 857
 858             if(height < nodeAttr.height) {
 859               highestHeightNode = *I;
 860               height = nodeAttr.height;
 861               MOB = nodeAttr.MOB;
 862             }
 863             else if(height ==  nodeAttr.height) {
 864               if(MOB > nodeAttr.height) {
 865                 highestHeightNode = *I;
 866                 height =  nodeAttr.height;
 867                 MOB = nodeAttr.MOB;
 868               }
 869             }
 870           }
 871
 872           //Append our node with greatest height to the NodeOrder
 873           if(find(FinalNodeOrder.begin(), FinalNodeOrder.end(), highestHeightNode) == FinalNodeOrder.end()) {
 874             DEBUG(std::cerr << "Adding node to Final Order: " << *highestHeightNode << "\n");
 875             FinalNodeOrder.push_back(highestHeightNode);
 876           }
 877
 878           //Remove V from IntersectOrder
 879           IntersectCurrent.erase(find(IntersectCurrent.begin(),
 880                                       IntersectCurrent.end(), highestHeightNode));
 881
 882
 883           //Intersect V's successors with CurrentSet
 884           for(MSchedGraphNode::succ_iterator P = highestHeightNode->succ_begin(),
 885                 E = highestHeightNode->succ_end(); P != E; ++P) {
 886             //if(lower_bound(CurrentSet->begin(),
 887             //     CurrentSet->end(), *P) != CurrentSet->end()) {
 888             if(find(CurrentSet->begin(), CurrentSet->end(), *P) != CurrentSet->end()) {
 889               if(ignoreEdge(highestHeightNode, *P))
 890                 continue;
 891               //If not already in Intersect, add
 892               if(find(IntersectCurrent.begin(), IntersectCurrent.end(), *P) == IntersectCurrent.end())
 893                 IntersectCurrent.push_back(*P);
 894             }
 895           }
 896         } //End while loop over Intersect Size
 897
 898         //Change direction
 899         order = BOTTOM_UP;
 900
 901         //Reset Intersect to reflect changes in OrderNodes
 902         IntersectCurrent.clear();
 903         predIntersect(*CurrentSet, IntersectCurrent);
 904
 905       } //End If TOP_DOWN
 906
 907         //Begin if BOTTOM_UP
 908       else {
 909         DEBUG(std::cerr << "Order is BOTTOM UP\n");
 910         while(IntersectCurrent.size() > 0) {
 911           DEBUG(std::cerr << "Intersection of size " << IntersectCurrent.size() << ", finding highest depth\n");
 912
 913           //dump intersection
 914           DEBUG(dumpIntersection(IntersectCurrent));
 915           //Get node with highest depth, if a tie, use one with lowest
 916           //MOB
 917           int MOB = 0;
 918           int depth = 0;
 919           MSchedGraphNode *highestDepthNode = IntersectCurrent[0];
 920
 921           for(std::vector<MSchedGraphNode*>::iterator I = IntersectCurrent.begin(),
 922                 E = IntersectCurrent.end(); I != E; ++I) {
 923             //Find node attribute in graph
 924             MSNodeAttributes nodeAttr= nodeToAttributesMap.find(*I)->second;
 925
 926             if(depth < nodeAttr.depth) {
 927               highestDepthNode = *I;
 928               depth = nodeAttr.depth;
 929               MOB = nodeAttr.MOB;
 930             }
 931             else if(depth == nodeAttr.depth) {
 932               if(MOB > nodeAttr.MOB) {
 933                 highestDepthNode = *I;
 934                 depth = nodeAttr.depth;
 935                 MOB = nodeAttr.MOB;
 936               }
 937             }
 938           }
 939
 940
 941
 942           //Append highest depth node to the NodeOrder
 943            if(find(FinalNodeOrder.begin(), FinalNodeOrder.end(), highestDepthNode) == FinalNodeOrder.end()) {
 944              DEBUG(std::cerr << "Adding node to Final Order: " << *highestDepthNode << "\n");
 945              FinalNodeOrder.push_back(highestDepthNode);
 946            }
 947           //Remove heightestDepthNode from IntersectOrder
 948           IntersectCurrent.erase(find(IntersectCurrent.begin(),
 949                                       IntersectCurrent.end(),highestDepthNode));
 950
 951
 952           //Intersect heightDepthNode's pred with CurrentSet
 953           for(MSchedGraphNode::pred_iterator P = highestDepthNode->pred_begin(),
 954                 E = highestDepthNode->pred_end(); P != E; ++P) {
 955             //if(lower_bound(CurrentSet->begin(),
 956             //     CurrentSet->end(), *P) != CurrentSet->end()) {
 957             if(find(CurrentSet->begin(), CurrentSet->end(), *P) != CurrentSet->end()) {
 958
 959               if(ignoreEdge(*P, highestDepthNode))
 960                 continue;
 961
 962             //If not already in Intersect, add
 963             if(find(IntersectCurrent.begin(),
 964                       IntersectCurrent.end(), *P) == IntersectCurrent.end())
 965                 IntersectCurrent.push_back(*P);
 966             }
 967           }
 968
 969         } //End while loop over Intersect Size
 970
 971           //Change order
 972         order = TOP_DOWN;
 973
 974         //Reset IntersectCurrent to reflect changes in OrderNodes
 975         IntersectCurrent.clear();
 976         succIntersect(*CurrentSet, IntersectCurrent);
 977         } //End if BOTTOM_DOWN
 978
 979     }
 980     //End Wrapping while loop
 981
 982   }//End for over all sets of nodes
 983
 984   //Return final Order
 985   //return FinalNodeOrder;
 986 }
 987
 988 void ModuloSchedulingPass::computeSchedule() {
 989
 990   bool success = false;
 991
 992   while(!success) {
 993
 994     //Loop over the final node order and process each node
 995     for(std::vector<MSchedGraphNode*>::iterator I = FinalNodeOrder.begin(),
 996           E = FinalNodeOrder.end(); I != E; ++I) {
 997
 998       //CalculateEarly and Late start
 999       int EarlyStart = -1;
1000       int LateStart = 99999; //Set to something higher then we would ever expect (FIXME)
1001       bool hasSucc = false;
1002       bool hasPred = false;
1003
1004       if(!(*I)->isBranch()) {
1005         //Loop over nodes in the schedule and determine if they are predecessors
1006         //or successors of the node we are trying to schedule
1007         for(MSSchedule::schedule_iterator nodesByCycle = schedule.begin(), nodesByCycleEnd = schedule.end();
1008             nodesByCycle != nodesByCycleEnd; ++nodesByCycle) {
1009
1010           //For this cycle, get the vector of nodes schedule and loop over it
1011           for(std::vector<MSchedGraphNode*>::iterator schedNode = nodesByCycle->second.begin(), SNE = nodesByCycle->second.end(); schedNode != SNE; ++schedNode) {
1012
1013             if((*I)->isPredecessor(*schedNode)) {
1014               if(!ignoreEdge(*schedNode, *I)) {
1015                 int diff = (*I)->getInEdge(*schedNode).getIteDiff();
1016                 int ES_Temp = nodesByCycle->first + (*schedNode)->getLatency() - diff * II;
1017         DEBUG(std::cerr << "Diff: " << diff << " Cycle: " << nodesByCycle->first << "\n");
1018                 DEBUG(std::cerr << "Temp EarlyStart: " << ES_Temp << " Prev EarlyStart: " << EarlyStart << "\n");
1019                 EarlyStart = std::max(EarlyStart, ES_Temp);
1020                 hasPred = true;
1021               }
1022             }
1023             if((*I)->isSuccessor(*schedNode)) {
1024               if(!ignoreEdge(*I,*schedNode)) {
1025                 int diff = (*schedNode)->getInEdge(*I).getIteDiff();
1026                 int LS_Temp = nodesByCycle->first - (*I)->getLatency() + diff * II;
1027                 DEBUG(std::cerr << "Diff: " << diff << " Cycle: " << nodesByCycle->first << "\n");
1028                 DEBUG(std::cerr << "Temp LateStart: " << LS_Temp << " Prev LateStart: " << LateStart << "\n");
1029                 LateStart = std::min(LateStart, LS_Temp);
1030                 hasSucc = true;
1031               }
1032             }
1033           }
1034         }
1035       }
1036       else {
1037         //WARNING: HACK! FIXME!!!!
1038         EarlyStart = II-1;
1039         LateStart = II-1;
1040         hasPred = 1;
1041         hasSucc = 1;
1042       }
1043
1044
1045       DEBUG(std::cerr << "Has Successors: " << hasSucc << ", Has Pred: " << hasPred << "\n");
1046       DEBUG(std::cerr << "EarlyStart: " << EarlyStart << ", LateStart: " << LateStart << "\n");
1047
1048       //Check if the node has no pred or successors and set Early Start to its ASAP
1049       if(!hasSucc && !hasPred)
1050         EarlyStart = nodeToAttributesMap.find(*I)->second.ASAP;
1051
1052       //Now, try to schedule this node depending upon its pred and successor in the schedule
1053       //already
1054       if(!hasSucc && hasPred)
1055         success = scheduleNode(*I, EarlyStart, (EarlyStart + II -1));
1056       else if(!hasPred && hasSucc)
1057         success = scheduleNode(*I, LateStart, (LateStart - II +1));
1058       else if(hasPred && hasSucc)
1059         success = scheduleNode(*I, EarlyStart, std::min(LateStart, (EarlyStart + II -1)));
1060       else
1061         success = scheduleNode(*I, EarlyStart, EarlyStart + II - 1);
1062
1063       if(!success) {
1064         ++II;
1065         schedule.clear();
1066         break;
1067       }
1068
1069     }
1070
1071     DEBUG(std::cerr << "Constructing Kernel\n");
1072     success = schedule.constructKernel(II);
1073     if(!success) {
1074       ++II;
1075       schedule.clear();
1076     }
1077   }
1078 }
1079
1080
1081 bool ModuloSchedulingPass::scheduleNode(MSchedGraphNode *node,
1082                                       int start, int end) {
1083   bool success = false;
1084
1085   DEBUG(std::cerr << *node << " (Start Cycle: " << start << ", End Cycle: " << end << ")\n");
1086
1087   //Make sure start and end are not negative
1088   if(start < 0)
1089     start = 0;
1090   if(end < 0)
1091     end = 0;
1092
1093   bool forward = true;
1094   if(start > end)
1095     forward = false;
1096
1097   bool increaseSC = true;
1098   int cycle = start ;
1099
1100
1101   while(increaseSC) {
1102
1103     increaseSC = false;
1104
1105     increaseSC = schedule.insert(node, cycle);
1106
1107     if(!increaseSC)
1108       return true;
1109
1110     //Increment cycle to try again
1111     if(forward) {
1112       ++cycle;
1113       DEBUG(std::cerr << "Increase cycle: " << cycle << "\n");
1114       if(cycle > end)
1115         return false;
1116     }
1117     else {
1118       --cycle;
1119       DEBUG(std::cerr << "Decrease cycle: " << cycle << "\n");
1120       if(cycle < end)
1121         return false;
1122     }
1123   }
1124
1125   return success;
1126 }
1127
1128 /*void ModuloSchedulingPass::saveValue(const MachineInstr *inst, std::set<const Value*> &valuestoSave, std::vector<Value*> *valuesForNode) {
1129   int numFound = 0;
1130   Instruction *tmp;
1131
1132   //For each value* in this inst that is a def, we want to save a copy
1133   //Target info
1134   const TargetInstrInfo & mii = target.getInstrInfo();
1135   for(unsigned i=0; i < inst->getNumOperands(); ++i) {
1136     //get machine operand
1137     const MachineOperand &mOp = inst->getOperand(i);
1138     if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) {
1139       //Save copy in tmpInstruction
1140       numFound++;
1141       tmp = TmpInstruction(mii.getMachineCodeFor(mOp.getVRegValue()),
1142                  mOp.getVRegValue());
1143       valuesForNode->push_back(tmp);
1144     }
1145   }
1146
1147   assert(numFound == 1 && "We should have only found one def to this virtual register!");
1148 }*/
1149
1150 void ModuloSchedulingPass::writePrologues(std::vector<MachineBasicBlock *> &prologues, const MachineBasicBlock *origBB, std::vector<BasicBlock*> &llvm_prologues) {
1151
1152   std::map<int, std::set<const MachineInstr*> > inKernel;
1153   int maxStageCount = 0;
1154
1155   for(MSSchedule::kernel_iterator I = schedule.kernel_begin(), E = schedule.kernel_end(); I != E; ++I) {
1156     maxStageCount = std::max(maxStageCount, I->second);
1157
1158     //Ignore the branch, we will handle this separately
1159     if(I->first->isBranch())
1160       continue;
1161
1162     //Put int the map so we know what instructions in each stage are in the kernel
1163     if(I->second > 0) {
1164       DEBUG(std::cerr << "Inserting instruction " << *(I->first->getInst()) << " into map at stage " << I->second << "\n");
1165       inKernel[I->second].insert(I->first->getInst());
1166     }
1167   }
1168
1169   //Now write the prologues
1170   for(int i = 1; i <= maxStageCount; ++i) {
1171     BasicBlock *llvmBB = new BasicBlock();
1172     MachineBasicBlock *machineBB = new MachineBasicBlock(llvmBB);
1173
1174     //Loop over original machine basic block. If we see an instruction from this
1175     //stage that is NOT in the kernel, then it needs to be added into the prologue
1176     //We go in order to preserve dependencies
1177     for(MachineBasicBlock::const_iterator MI = origBB->begin(), ME = origBB->end(); ME != MI; ++MI) {
1178       if(inKernel[i].count(&*MI)) {
1179         inKernel[i].erase(&*MI);
1180         if(inKernel[i].size() <= 0)
1181           break;
1182         else
1183           continue;
1184       }
1185       else {
1186         DEBUG(std::cerr << "Writing instruction to prologue\n");
1187         machineBB->push_back(MI->clone());
1188       }
1189     }
1190
1191     (((MachineBasicBlock*)origBB)->getParent())->getBasicBlockList().push_back(machineBB);
1192     prologues.push_back(machineBB);
1193     llvm_prologues.push_back(llvmBB);
1194   }
1195 }
1196
1197 void ModuloSchedulingPass::writeEpilogues(std::vector<MachineBasicBlock *> &epilogues, const MachineBasicBlock *origBB, std::vector<BasicBlock*> &llvm_epilogues) {
1198   std::map<int, std::set<const MachineInstr*> > inKernel;
1199   int maxStageCount = 0;
1200   for(MSSchedule::kernel_iterator I = schedule.kernel_begin(), E = schedule.kernel_end(); I != E; ++I) {
1201     maxStageCount = std::max(maxStageCount, I->second);
1202
1203     //Ignore the branch, we will handle this separately
1204     if(I->first->isBranch())
1205       continue;
1206
1207     //Put int the map so we know what instructions in each stage are in the kernel
1208     if(I->second > 0) {
1209       DEBUG(std::cerr << "Inserting instruction " << *(I->first->getInst()) << " into map at stage " << I->second << "\n");
1210       inKernel[I->second].insert(I->first->getInst());
1211     }
1212   }
1213
1214   //Now write the epilogues
1215   for(int i = 1; i <= maxStageCount; ++i) {
1216     BasicBlock *llvmBB = new BasicBlock();
1217     MachineBasicBlock *machineBB = new MachineBasicBlock(llvmBB);
1218
1219     bool last = false;
1220     for(MachineBasicBlock::const_iterator MI = origBB->begin(), ME = origBB->end(); ME != MI; ++MI) {
1221
1222       if(!last) {
1223         if(inKernel[i].count(&*MI)) {
1224           machineBB->push_back(MI->clone());
1225           inKernel[i].erase(&*MI);
1226           if(inKernel[i].size() <= 0)
1227             last = true;
1228         }
1229       }
1230
1231       else
1232         machineBB->push_back(MI->clone());
1233
1234
1235     }
1236     (((MachineBasicBlock*)origBB)->getParent())->getBasicBlockList().push_back(machineBB);
1237     epilogues.push_back(machineBB);
1238     llvm_epilogues.push_back(llvmBB);
1239   }
1240
1241 }
1242
1243
1244
1245 void ModuloSchedulingPass::reconstructLoop(const MachineBasicBlock *BB) {
1246
1247   //The new loop will consist of an prologue, the kernel, and one or more epilogues.
1248
1249   std::vector<MachineBasicBlock*> prologues;
1250   std::vector<BasicBlock*> llvm_prologues;
1251
1252   //Write prologue
1253   writePrologues(prologues, BB, llvm_prologues);
1254
1255   //Print out prologue
1256   for(std::vector<MachineBasicBlock*>::iterator I = prologues.begin(), E = prologues.end();
1257       I != E; ++I) {
1258     std::cerr << "PROLOGUE\n";
1259     (*I)->print(std::cerr);
1260   }
1261
1262
1263   std::vector<MachineBasicBlock*> epilogues;
1264   std::vector<BasicBlock*> llvm_epilogues;
1265
1266   //Write epilogues
1267   writeEpilogues(epilogues, BB, llvm_epilogues);
1268
1269   //Print out prologue
1270   for(std::vector<MachineBasicBlock*>::iterator I = epilogues.begin(), E = epilogues.end();
1271       I != E; ++I) {
1272     std::cerr << "EPILOGUE\n";
1273     (*I)->print(std::cerr);
1274   }
1275
1276   //create a vector of epilogues corresponding to each stage
1277   /*std::vector<MachineBasicBlock*> epilogues;
1278
1279     //Create kernel
1280   MachineBasicBlock *kernel = new MachineBasicBlock();
1281
1282   //keep track of stage count
1283   int stageCount = 0;
1284
1285   //Target info
1286   const TargetInstrInfo & mii = target.getInstrInfo();
1287
1288   //Map for creating MachinePhis
1289   std::map<MSchedGraphNode *, std::vector<Value*> > nodeAndValueMap;
1290
1291
1292   //Loop through the kernel and clone instructions that need to be put into the prologue
1293   for(MSSchedule::kernel_iterator I = schedule.kernel_begin(), E = schedule.kernel_end(); I != E; ++I) {
1294     //For each pair see if the stage is greater then 0
1295     //if so, then ALL instructions before this in the original loop, need to be
1296     //copied into the prologue
1297     MachineBasicBlock::const_iterator actualInst;
1298
1299
1300     //ignore branch
1301     if(I->first->isBranch())
1302       continue;
1303
1304     if(I->second > 0) {
1305
1306       assert(I->second >= stageCount && "Visiting instruction from previous stage count.\n");
1307
1308
1309       //Make a set that has all the Value*'s that we read
1310       std::set<const Value*> valuesToSave;
1311
1312       //For this instruction, get the Value*'s that it reads and put them into the set.
1313       //Assert if there is an operand of another type that we need to save
1314       const MachineInstr *inst = I->first->getInst();
1315       for(unsigned i=0; i < inst->getNumOperands(); ++i) {
1316         //get machine operand
1317         const MachineOperand &mOp = inst->getOperand(i);
1318
1319         if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isUse()) {
1320           //find the value in the map
1321           if (const Value* srcI = mOp.getVRegValue())
1322             valuesToSave.insert(srcI);
1323         }
1324
1325         if(mOp.getType() != MachineOperand::MO_VirtualRegister && mOp.isUse()) {
1326           assert("Our assumption is wrong. We have another type of register that needs to be saved\n");
1327         }
1328       }
1329
1330       //Check if we skipped a stage count, we need to add that stuff here
1331       if(I->second - stageCount > 1) {
1332         int temp = stageCount;
1333         while(I->second - temp > 1) {
1334           for(MachineBasicBlock::const_iterator MI = BB->begin(), ME = BB->end(); ME != MI; ++MI) {
1335             //Check that MI is not a branch before adding, we add branches separately
1336             if(!mii.isBranch(MI->getOpcode()) && !mii.isNop(MI->getOpcode())) {
1337               prologue->push_back(MI->clone());
1338               saveValue(&*MI, valuesToSave);
1339             }
1340           }
1341           ++temp;
1342         }
1343       }
1344
1345       if(I->second == stageCount)
1346         continue;
1347
1348       stageCount = I->second;
1349       DEBUG(std::cerr << "Found Instruction from Stage > 0\n");
1350       //Loop over instructions in original basic block and clone them. Add to the prologue
1351       for (MachineBasicBlock::const_iterator MI = BB->begin(), e = BB->end(); MI != e; ++MI) {
1352         if(&*MI == I->first->getInst()) {
1353           actualInst = MI;
1354           break;
1355         }
1356         else {
1357           //Check that MI is not a branch before adding, we add branches separately
1358           if(!mii.isBranch(MI->getOpcode()) && !mii.isNop(MI->getOpcode()))
1359             prologue->push_back(MI->clone());
1360         }
1361       }
1362
1363       //Now add in all instructions from this one on to its corresponding epilogue
1364       MachineBasicBlock *epi = new MachineBasicBlock();
1365       epilogues.push_back(epi);
1366
1367       for(MachineBasicBlock::const_iterator MI = actualInst, ME = BB->end(); ME != MI; ++MI) {
1368         //Check that MI is not a branch before adding, we add branches separately
1369         if(!mii.isBranch(MI->getOpcode()) && !mii.isNop(MI->getOpcode()))
1370           epi->push_back(MI->clone());
1371       }
1372     }
1373   }
1374
1375   //Create kernel
1376    for(MSSchedule::kernel_iterator I = schedule.kernel_begin(),
1377          E = schedule.kernel_end(); I != E; ++I) {
1378      kernel->push_back(I->first->getInst()->clone());
1379
1380      }
1381
1382   //Debug stuff
1383   ((MachineBasicBlock*)BB)->getParent()->getBasicBlockList().push_back(prologue);
1384   std::cerr << "PROLOGUE:\n";
1385   prologue->print(std::cerr);
1386
1387   ((MachineBasicBlock*)BB)->getParent()->getBasicBlockList().push_back(kernel);
1388   std::cerr << "KERNEL: \n";
1389   kernel->print(std::cerr);
1390
1391   for(std::vector<MachineBasicBlock*>::iterator MBB = epilogues.begin(), ME = epilogues.end();
1392       MBB != ME; ++MBB) {
1393     std::cerr << "EPILOGUE:\n";
1394     ((MachineBasicBlock*)BB)->getParent()->getBasicBlockList().push_back(*MBB);
1395     (*MBB)->print(std::cerr);
1396     }*/
1397
1398
1399
1400 }
1401