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