lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp

   1 //===- ModuloScheduling.cpp - Modulo Software Pipelining ------------------===//
   2 //
   3 // Implements the llvm/CodeGen/ModuloScheduling.h interface
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "llvm/BasicBlock.h"
   8 #include "llvm/Constants.h"
   9 #include "llvm/iTerminators.h"
  10 #include "llvm/iPHINode.h"
  11 #include "llvm/CodeGen/MachineInstr.h"
  12 #include "llvm/CodeGen/MachineCodeForInstruction.h"
  13 #include "llvm/CodeGen/MachineFunction.h"
  14 #include "llvm/CodeGen/InstrSelection.h"
  15 #include "llvm/Target/TargetSchedInfo.h"
  16 #include "llvm/Target/TargetMachine.h"
  17 #include "Support/CommandLine.h"
  18 #include "Support/Statistic.h"
  19 #include "ModuloSchedGraph.h"
  20 #include "ModuloScheduling.h"
  21 #include <algorithm>
  22 #include <fstream>
  23
  24 //************************************************************
  25 // printing Debug information
  26 // ModuloSchedDebugLevel stores the value of debug level
  27 // modsched_os is the ostream to dump debug information, which is written into
  28 // the file 'moduloSchedDebugInfo.output'
  29 // see ModuloSchedulingPass::runOnFunction()
  30 //************************************************************
  31
  32 ModuloSchedDebugLevel_t ModuloSchedDebugLevel;
  33
  34 cl::opt<ModuloSchedDebugLevel_t,true>
  35 SDL_opt("modsched", cl::Hidden, cl::location(ModuloSchedDebugLevel),
  36         cl::desc("enable modulo scheduling debugging information"),
  37         cl::values(clEnumValN(ModuloSchedDebugLevel_NoDebugInfo,
  38                               "none", "disable debug output"),
  39                    clEnumValN(ModuloSchedDebugLevel_PrintSchedule,
  40                               "psched", "print original and new schedule"),
  41                    clEnumValN(ModuloSchedDebugLevel_PrintScheduleProcess,
  42                               "pschedproc",
  43                               "print how the new schdule is produced"),
  44                    0));
  45
  46 // Computes the schedule and inserts epilogue and prologue
  47 //
  48 void
  49 ModuloScheduling::instrScheduling(){
  50
  51
  52   if (ModuloScheduling::printScheduleProcess())
  53     DEBUG_PRINT(std::cerr << "************ computing modulo schedule ***********\n");
  54
  55   const TargetSchedInfo & msi = target.getSchedInfo();
  56
  57   //number of issue slots in the in each cycle
  58   int numIssueSlots = msi.maxNumIssueTotal;
  59
  60   //compute the schedule
  61   bool success = false;
  62   while (!success) {
  63     //clear memory from the last round and initialize if necessary
  64     clearInitMem(msi);
  65
  66     //compute schedule and coreSchedule with the current II
  67     success = computeSchedule();
  68
  69     if (!success) {
  70       II++;
  71       if (ModuloScheduling::printScheduleProcess())
  72         DEBUG_PRINT(std::cerr << "increase II  to " << II << "\n");
  73     }
  74   }
  75
  76   //print the final schedule
  77   dumpFinalSchedule();
  78
  79   //the schedule has been computed
  80   //create epilogue, prologue and kernel BasicBlock
  81
  82   //find the successor for this BasicBlock
  83   BasicBlock *succ_bb = getSuccBB(bb);
  84
  85   //print the original BasicBlock if necessary
  86   if (ModuloScheduling::printSchedule()) {
  87     DEBUG_PRINT(std::cerr << "dumping the orginal block\n");
  88     graph.dump(bb);
  89   }
  90   //construction of prologue, kernel and epilogue
  91
  92   /*
  93   BasicBlock *kernel = bb->splitBasicBlock(bb->begin());
  94   BasicBlock *prologue = bb;
  95   BasicBlock *epilogue = kernel->splitBasicBlock(kernel->begin());
  96   */
  97
  98   // Construct prologue
  99   /*constructPrologue(prologue);*/
 100
 101   // Construct kernel
 102
 103   /*constructKernel(prologue, kernel, epilogue);*/
 104
 105   // Construct epilogue
 106
 107   /*constructEpilogue(epilogue, succ_bb);*/
 108
 109   //print the BasicBlocks if necessary
 110 //    if (0){
 111 //      DEBUG_PRINT(std::cerr << "dumping the prologue block:\n");
 112 //      graph.dump(prologue);
 113 //      DEBUG_PRINT(std::cerr << "dumping the kernel block\n");
 114 //      graph.dump(kernel);
 115 //      DEBUG_PRINT(std::cerr << "dumping the epilogue block\n");
 116 //      graph.dump(epilogue);
 117 //    }
 118
 119 }
 120
 121
 122 // Clear memory from the last round and initialize if necessary
 123 //
 124
 125 void
 126 ModuloScheduling::clearInitMem(const TargetSchedInfo & msi){
 127
 128   unsigned numIssueSlots = msi.maxNumIssueTotal;
 129   // clear nodeScheduled from the last round
 130   if (ModuloScheduling::printScheduleProcess()) {
 131     DEBUG_PRINT(std::cerr << "***** new round  with II= " << II << " ***********\n");
 132     DEBUG_PRINT(std::cerr <<
 133         " ************clear the vector nodeScheduled*************\n");
 134   }
 135   nodeScheduled.clear();
 136
 137   // clear resourceTable from the last round and reset it
 138   resourceTable.clear();
 139   for (unsigned i = 0; i < II; ++i)
 140     resourceTable.push_back(msi.resourceNumVector);
 141
 142   // clear the schdule and coreSchedule from the last round
 143   schedule.clear();
 144   coreSchedule.clear();
 145
 146   // create a coreSchedule of size II*numIssueSlots
 147   // each entry is NULL
 148   while (coreSchedule.size() < II) {
 149     std::vector < ModuloSchedGraphNode * >*newCycle =
 150         new std::vector < ModuloSchedGraphNode * >();
 151     for (unsigned k = 0; k < numIssueSlots; ++k)
 152       newCycle->push_back(NULL);
 153     coreSchedule.push_back(*newCycle);
 154   }
 155 }
 156
 157 // Compute schedule and coreSchedule with the current II
 158 //
 159 bool
 160 ModuloScheduling::computeSchedule(){
 161
 162
 163   if (ModuloScheduling::printScheduleProcess())
 164     DEBUG_PRINT(std::cerr << "start to compute schedule\n");
 165
 166   // Loop over the ordered nodes
 167   for (NodeVec::const_iterator I = oNodes.begin(); I != oNodes.end(); ++I) {
 168     // Try to schedule for node I
 169     if (ModuloScheduling::printScheduleProcess())
 170       dumpScheduling();
 171     ModuloSchedGraphNode *node = *I;
 172
 173     // Compute whether this node has successor(s)
 174     bool succ = true;
 175
 176     // Compute whether this node has predessor(s)
 177     bool pred = true;
 178
 179     NodeVec schSucc = graph.vectorConj(nodeScheduled, graph.succSet(node));
 180     if (schSucc.empty())
 181       succ = false;
 182     NodeVec schPred = graph.vectorConj(nodeScheduled, graph.predSet(node));
 183     if (schPred.empty())
 184       pred = false;
 185
 186     //startTime: the earliest time we will try to schedule this node
 187     //endTime: the latest time we will try to schedule this node
 188     int startTime, endTime;
 189
 190     //node's earlyStart: possible earliest time to schedule this node
 191     //node's lateStart: possible latest time to schedule this node
 192     node->setEarlyStart(-1);
 193     node->setLateStart(9999);
 194
 195     //this node has predessor but no successor
 196     if (!succ && pred) {
 197       // This node's earlyStart is it's predessor's schedule time + the edge
 198       // delay - the iteration difference* II
 199       for (unsigned i = 0; i < schPred.size(); i++) {
 200         ModuloSchedGraphNode *predNode = schPred[i];
 201         SchedGraphEdge *edge =
 202             graph.getMaxDelayEdge(predNode->getNodeId(),
 203                                   node->getNodeId());
 204         int temp =
 205             predNode->getSchTime() + edge->getMinDelay() -
 206             edge->getIteDiff() * II;
 207         node->setEarlyStart(std::max(node->getEarlyStart(), temp));
 208       }
 209       startTime = node->getEarlyStart();
 210       endTime = node->getEarlyStart() + II - 1;
 211     }
 212     // This node has a successor but no predecessor
 213     if (succ && !pred) {
 214       for (unsigned i = 0; i < schSucc.size(); ++i) {
 215         ModuloSchedGraphNode *succNode = schSucc[i];
 216         SchedGraphEdge *edge =
 217             graph.getMaxDelayEdge(succNode->getNodeId(),
 218                                   node->getNodeId());
 219         int temp =
 220             succNode->getSchTime() - edge->getMinDelay() +
 221             edge->getIteDiff() * II;
 222         node->setLateStart(std::min(node->getEarlyStart(), temp));
 223       }
 224       startTime = node->getLateStart() - II + 1;
 225       endTime = node->getLateStart();
 226     }
 227     // This node has both successors and predecessors
 228     if (succ && pred) {
 229       for (unsigned i = 0; i < schPred.size(); ++i) {
 230         ModuloSchedGraphNode *predNode = schPred[i];
 231         SchedGraphEdge *edge =
 232             graph.getMaxDelayEdge(predNode->getNodeId(),
 233                                   node->getNodeId());
 234         int temp =
 235             predNode->getSchTime() + edge->getMinDelay() -
 236             edge->getIteDiff() * II;
 237         node->setEarlyStart(std::max(node->getEarlyStart(), temp));
 238       }
 239       for (unsigned i = 0; i < schSucc.size(); ++i) {
 240         ModuloSchedGraphNode *succNode = schSucc[i];
 241         SchedGraphEdge *edge =
 242             graph.getMaxDelayEdge(succNode->getNodeId(),
 243                                   node->getNodeId());
 244         int temp =
 245             succNode->getSchTime() - edge->getMinDelay() +
 246             edge->getIteDiff() * II;
 247         node->setLateStart(std::min(node->getEarlyStart(), temp));
 248       }
 249       startTime = node->getEarlyStart();
 250       endTime = std::min(node->getLateStart(),
 251                          node->getEarlyStart() + ((int) II) - 1);
 252     }
 253     //this node has no successor or predessor
 254     if (!succ && !pred) {
 255       node->setEarlyStart(node->getASAP());
 256       startTime = node->getEarlyStart();
 257       endTime = node->getEarlyStart() + II - 1;
 258     }
 259     //try to schedule this node based on the startTime and endTime
 260     if (ModuloScheduling::printScheduleProcess())
 261       DEBUG_PRINT(std::cerr << "scheduling the node " << (*I)->getNodeId() << "\n");
 262
 263     bool success =
 264         this->ScheduleNode(node, startTime, endTime, nodeScheduled);
 265     if (!success)
 266       return false;
 267   }
 268   return true;
 269 }
 270
 271
 272 // Get the successor of the BasicBlock
 273 //
 274 BasicBlock *
 275 ModuloScheduling::getSuccBB(BasicBlock *bb){
 276
 277   BasicBlock *succ_bb;
 278   for (unsigned i = 0; i < II; ++i)
 279     for (unsigned j = 0; j < coreSchedule[i].size(); ++j)
 280       if (coreSchedule[i][j]) {
 281         const Instruction *ist = coreSchedule[i][j]->getInst();
 282
 283         //we can get successor from the BranchInst instruction
 284         //assume we only have one successor (besides itself) here
 285         if (BranchInst::classof(ist)) {
 286           BranchInst *bi = (BranchInst *) ist;
 287           assert(bi->isConditional() &&
 288                  "the branchInst is not a conditional one");
 289           assert(bi->getNumSuccessors() == 2
 290                  && " more than two successors?");
 291           BasicBlock *bb1 = bi->getSuccessor(0);
 292           BasicBlock *bb2 = bi->getSuccessor(1);
 293           assert((bb1 == bb || bb2 == bb) &&
 294                  " None of its successors is itself?");
 295           if (bb1 == bb)
 296             succ_bb = bb2;
 297           else
 298             succ_bb = bb1;
 299           return succ_bb;
 300         }
 301       }
 302   assert(0 && "NO Successor?");
 303   return NULL;
 304 }
 305
 306
 307 // Get the predecessor of the BasicBlock
 308 //
 309 BasicBlock *
 310 ModuloScheduling::getPredBB(BasicBlock *bb){
 311
 312   BasicBlock *pred_bb;
 313   for (unsigned i = 0; i < II; ++i)
 314     for (unsigned j = 0; j < coreSchedule[i].size(); ++j)
 315       if (coreSchedule[i][j]) {
 316         const Instruction *ist = coreSchedule[i][j]->getInst();
 317
 318         //we can get predecessor from the PHINode instruction
 319         //assume we only have one predecessor (besides itself) here
 320         if (PHINode::classof(ist)) {
 321           PHINode *phi = (PHINode *) ist;
 322           assert(phi->getNumIncomingValues() == 2 &&
 323                  " the number of incoming value is not equal to two? ");
 324           BasicBlock *bb1 = phi->getIncomingBlock(0);
 325           BasicBlock *bb2 = phi->getIncomingBlock(1);
 326           assert((bb1 == bb || bb2 == bb) &&
 327                  " None of its predecessor is itself?");
 328           if (bb1 == bb)
 329             pred_bb = bb2;
 330           else
 331             pred_bb = bb1;
 332           return pred_bb;
 333         }
 334       }
 335   assert(0 && " no predecessor?");
 336   return NULL;
 337 }
 338
 339
 340 // Construct the prologue
 341 //
 342 void
 343 ModuloScheduling::constructPrologue(BasicBlock *prologue){
 344
 345   InstListType & prologue_ist = prologue->getInstList();
 346   vvNodeType & tempSchedule_prologue =
 347       *(new std::vector<std::vector<ModuloSchedGraphNode*> >(schedule));
 348
 349   //compute the schedule for prologue
 350   unsigned round = 0;
 351   unsigned scheduleSize = schedule.size();
 352   while (round < scheduleSize / II) {
 353     round++;
 354     for (unsigned i = 0; i < scheduleSize; ++i) {
 355       if (round * II + i >= scheduleSize)
 356         break;
 357       for (unsigned j = 0; j < schedule[i].size(); ++j) {
 358         if (schedule[i][j]) {
 359           assert(tempSchedule_prologue[round * II + i][j] == NULL &&
 360                  "table not consitent with core table");
 361           // move the schedule one iteration ahead and overlap with the original
 362           tempSchedule_prologue[round * II + i][j] = schedule[i][j];
 363         }
 364       }
 365     }
 366   }
 367
 368   // Clear the clone memory in the core schedule instructions
 369   clearCloneMemory();
 370
 371   // Fill in the prologue
 372   for (unsigned i = 0; i < ceil(1.0 * scheduleSize / II - 1) * II; ++i)
 373     for (unsigned j = 0; j < tempSchedule_prologue[i].size(); ++j)
 374       if (tempSchedule_prologue[i][j]) {
 375
 376         //get the instruction
 377         Instruction *orn =
 378             (Instruction *) tempSchedule_prologue[i][j]->getInst();
 379
 380         //made a clone of it
 381         Instruction *cln = cloneInstSetMemory(orn);
 382
 383         //insert the instruction
 384         prologue_ist.insert(prologue_ist.back(), cln);
 385
 386         //if there is PHINode in the prologue, the incoming value from itself
 387         //should be removed because it is not a loop any longer
 388         if (PHINode::classof(cln)) {
 389           PHINode *phi = (PHINode *) cln;
 390           phi->removeIncomingValue(phi->getParent());
 391         }
 392       }
 393 }
 394
 395
 396 // Construct the kernel BasicBlock
 397 //
 398 void
 399 ModuloScheduling::constructKernel(BasicBlock *prologue,
 400                                        BasicBlock *kernel,
 401                                        BasicBlock *epilogue){
 402
 403   //*************fill instructions in the kernel****************
 404   InstListType & kernel_ist = kernel->getInstList();
 405   BranchInst *brchInst;
 406   PHINode *phiInst, *phiCln;
 407
 408   for (unsigned i = 0; i < coreSchedule.size(); ++i)
 409     for (unsigned j = 0; j < coreSchedule[i].size(); ++j)
 410       if (coreSchedule[i][j]) {
 411
 412         // Take care of branch instruction differently with normal instructions
 413         if (BranchInst::classof(coreSchedule[i][j]->getInst())) {
 414           brchInst = (BranchInst *) coreSchedule[i][j]->getInst();
 415           continue;
 416         }
 417         // Take care of PHINode instruction differently with normal instructions
 418         if (PHINode::classof(coreSchedule[i][j]->getInst())) {
 419           phiInst = (PHINode *) coreSchedule[i][j]->getInst();
 420           Instruction *cln = cloneInstSetMemory(phiInst);
 421           kernel_ist.insert(kernel_ist.back(), cln);
 422           phiCln = (PHINode *) cln;
 423           continue;
 424         }
 425         //for normal instructions: made a clone and insert it in the kernel_ist
 426         Instruction *cln =
 427             cloneInstSetMemory((Instruction *) coreSchedule[i][j]->
 428                                getInst());
 429         kernel_ist.insert(kernel_ist.back(), cln);
 430       }
 431   // The two incoming BasicBlock for PHINode is the prologue and the kernel
 432   // (itself)
 433   phiCln->setIncomingBlock(0, prologue);
 434   phiCln->setIncomingBlock(1, kernel);
 435
 436   // The incoming value for the kernel (itself) is the new value which is
 437   // computed in the kernel
 438   Instruction *originalVal = (Instruction *) phiInst->getIncomingValue(1);
 439   phiCln->setIncomingValue(1, originalVal->getClone());
 440
 441   // Make a clone of the branch instruction and insert it in the end
 442   BranchInst *cln = (BranchInst *) cloneInstSetMemory(brchInst);
 443   kernel_ist.insert(kernel_ist.back(), cln);
 444
 445   // delete the unconditional branch instruction, which is generated when
 446   // splitting the basicBlock
 447   kernel_ist.erase(--kernel_ist.end());
 448
 449   // set the first successor to itself
 450   cln->setSuccessor(0, kernel);
 451   // set the second successor to eiplogue
 452   cln->setSuccessor(1, epilogue);
 453
 454   //*****change the condition*******
 455
 456   //get the condition instruction
 457   Instruction *cond = (Instruction *) cln->getCondition();
 458
 459   //get the condition's second operand, it should be a constant
 460   Value *operand = cond->getOperand(1);
 461   assert(ConstantSInt::classof(operand));
 462
 463   //change the constant in the condtion instruction
 464   ConstantSInt *iteTimes =
 465       ConstantSInt::get(operand->getType(),
 466                         ((ConstantSInt *) operand)->getValue() - II + 1);
 467   cond->setOperand(1, iteTimes);
 468
 469 }
 470
 471
 472 // Construct the epilogue
 473 //
 474 void
 475 ModuloScheduling::constructEpilogue(BasicBlock *epilogue,
 476                                          BasicBlock *succ_bb){
 477
 478   //compute the schedule for epilogue
 479   vvNodeType &tempSchedule_epilogue =
 480       *(new std::vector<std::vector<ModuloSchedGraphNode*> >(schedule));
 481   unsigned scheduleSize = schedule.size();
 482   int round = 0;
 483   while (round < ceil(1.0 * scheduleSize / II) - 1) {
 484     round++;
 485     for (unsigned i = 0; i < scheduleSize; i++) {
 486       if (i + round * II >= scheduleSize)
 487         break;
 488       for (unsigned j = 0; j < schedule[i].size(); j++)
 489         if (schedule[i + round * II][j]) {
 490           assert(tempSchedule_epilogue[i][j] == NULL
 491                  && "table not consitant with core table");
 492
 493           //move the schdule one iteration behind and overlap
 494           tempSchedule_epilogue[i][j] = schedule[i + round * II][j];
 495         }
 496     }
 497   }
 498
 499   //fill in the epilogue
 500   InstListType & epilogue_ist = epilogue->getInstList();
 501   for (unsigned i = II; i < scheduleSize; i++)
 502     for (unsigned j = 0; j < tempSchedule_epilogue[i].size(); j++)
 503       if (tempSchedule_epilogue[i][j]) {
 504         Instruction *inst =
 505             (Instruction *) tempSchedule_epilogue[i][j]->getInst();
 506
 507         //BranchInst and PHINode should be treated differently
 508         //BranchInst:unecessary, simly omitted
 509         //PHINode: omitted
 510         if (!BranchInst::classof(inst) && !PHINode::classof(inst)) {
 511           //make a clone instruction and insert it into the epilogue
 512           Instruction *cln = cloneInstSetMemory(inst);
 513           epilogue_ist.push_front(cln);
 514         }
 515       }
 516
 517   //*************delete the original instructions****************//
 518   //to delete the original instructions, we have to make sure their use is zero
 519
 520   //update original core instruction's uses, using its clone instread
 521   for (unsigned i = 0; i < II; i++)
 522     for (unsigned j = 0; j < coreSchedule[i].size(); j++) {
 523       if (coreSchedule[i][j])
 524         updateUseWithClone((Instruction *) coreSchedule[i][j]->getInst());
 525     }
 526
 527   //erase these instructions
 528   for (unsigned i = 0; i < II; i++)
 529     for (unsigned j = 0; j < coreSchedule[i].size(); j++)
 530       if (coreSchedule[i][j]) {
 531         Instruction *ist = (Instruction *) coreSchedule[i][j]->getInst();
 532         ist->getParent()->getInstList().erase(ist);
 533       }
 534
 535
 536
 537   //finally, insert an unconditional branch instruction at the end
 538   epilogue_ist.push_back(new BranchInst(succ_bb));
 539
 540 }
 541
 542
 543 //------------------------------------------------------------------------------
 544 //this function replace the value(instruction) ist in other instructions with
 545 //its latest clone i.e. after this function is called, the ist is not used
 546 //anywhere and it can be erased.
 547 //------------------------------------------------------------------------------
 548 void
 549 ModuloScheduling::updateUseWithClone(Instruction * ist){
 550
 551
 552   while (ist->use_size() > 0) {
 553     bool destroyed = false;
 554
 555     //other instruction is using this value ist
 556     assert(Instruction::classof(*ist->use_begin()));
 557     Instruction *inst = (Instruction *) (*ist->use_begin());
 558
 559     for (unsigned i = 0; i < inst->getNumOperands(); i++)
 560       if (inst->getOperand(i) == ist && ist->getClone()) {
 561         // if the instruction is TmpInstruction, simly delete it because it has
 562         // no parent and it does not belongs to any BasicBlock
 563         if (TmpInstruction::classof(inst)) {
 564           delete inst;
 565           destroyed = true;
 566           break;
 567         }
 568
 569         //otherwise, set the instruction's operand to the value's clone
 570         inst->setOperand(i, ist->getClone());
 571
 572         //the use from the original value ist is destroyed
 573         destroyed = true;
 574         break;
 575       }
 576     if (!destroyed) {
 577       //if the use can not be destroyed , something is wrong
 578       inst->dump();
 579       assert(0 && "this use can not be destroyed");
 580     }
 581   }
 582
 583 }
 584
 585
 586 //********************************************************
 587 //this function clear all clone mememoy
 588 //i.e. set all instruction's clone memory to NULL
 589 //*****************************************************
 590 void
 591 ModuloScheduling::clearCloneMemory(){
 592
 593   for (unsigned i = 0; i < coreSchedule.size(); i++)
 594     for (unsigned j = 0; j < coreSchedule[i].size(); j++)
 595       if (coreSchedule[i][j])
 596         ((Instruction *) coreSchedule[i][j]->getInst())->clearClone();
 597
 598 }
 599
 600
 601 //******************************************************************************
 602 // this function make a clone of the instruction orn the cloned instruction will
 603 // use the orn's operands' latest clone as its operands it is done this way
 604 // because LLVM is in SSA form and we should use the correct value
 605 //this fuction also update the instruction orn's latest clone memory
 606 //******************************************************************************
 607 Instruction *
 608 ModuloScheduling::cloneInstSetMemory(Instruction * orn){
 609
 610   // make a clone instruction
 611   Instruction *cln = orn->clone();
 612
 613   // update the operands
 614   for (unsigned k = 0; k < orn->getNumOperands(); k++) {
 615     const Value *op = orn->getOperand(k);
 616     if (Instruction::classof(op) && ((Instruction *) op)->getClone()) {
 617       Instruction *op_inst = (Instruction *) op;
 618       cln->setOperand(k, op_inst->getClone());
 619     }
 620   }
 621
 622   // update clone memory
 623   orn->setClone(cln);
 624   return cln;
 625 }
 626
 627
 628
 629 bool
 630 ModuloScheduling::ScheduleNode(ModuloSchedGraphNode * node,
 631                                     unsigned start, unsigned end,
 632                                     NodeVec & nodeScheduled){
 633
 634   const TargetSchedInfo & msi = target.getSchedInfo();
 635   unsigned int numIssueSlots = msi.maxNumIssueTotal;
 636
 637   if (ModuloScheduling::printScheduleProcess())
 638     DEBUG_PRINT(std::cerr << "startTime= " << start << " endTime= " << end << "\n");
 639   bool isScheduled = false;
 640   for (unsigned i = start; i <= end; i++) {
 641     if (ModuloScheduling::printScheduleProcess())
 642       DEBUG_PRINT(std::cerr << " now try cycle " << i << ":" << "\n");
 643     for (unsigned j = 0; j < numIssueSlots; j++) {
 644       unsigned int core_i = i % II;
 645       unsigned int core_j = j;
 646       if (ModuloScheduling::printScheduleProcess())
 647         DEBUG_PRINT(std::cerr << "\t Trying slot " << j << "...........");
 648       //check the resouce table, make sure there is no resource conflicts
 649       const Instruction *instr = node->getInst();
 650       MachineCodeForInstruction & tempMvec =
 651           MachineCodeForInstruction::get(instr);
 652       bool resourceConflict = false;
 653       const TargetInstrInfo & mii = msi.getInstrInfo();
 654
 655       if (coreSchedule.size() < core_i + 1
 656           || !coreSchedule[core_i][core_j]) {
 657         //this->dumpResourceUsageTable();
 658         int latency = 0;
 659         for (unsigned k = 0; k < tempMvec.size(); k++) {
 660           MachineInstr *minstr = tempMvec[k];
 661           InstrRUsage rUsage = msi.getInstrRUsage(minstr->getOpCode());
 662           std::vector < std::vector < resourceId_t > >resources
 663               = rUsage.resourcesByCycle;
 664           updateResourceTable(resources, i + latency);
 665           latency += std::max(mii.minLatency(minstr->getOpCode()), 1);
 666         }
 667
 668         //this->dumpResourceUsageTable();
 669
 670         latency = 0;
 671         if (resourceTableNegative()) {
 672
 673           //undo-update the resource table
 674           for (unsigned k = 0; k < tempMvec.size(); k++) {
 675             MachineInstr *minstr = tempMvec[k];
 676             InstrRUsage rUsage = msi.getInstrRUsage(minstr->getOpCode());
 677             std::vector < std::vector < resourceId_t > >resources
 678                 = rUsage.resourcesByCycle;
 679             undoUpdateResourceTable(resources, i + latency);
 680             latency += std::max(mii.minLatency(minstr->getOpCode()), 1);
 681           }
 682           resourceConflict = true;
 683         }
 684       }
 685       if (!resourceConflict && !coreSchedule[core_i][core_j]) {
 686         if (ModuloScheduling::printScheduleProcess()) {
 687           DEBUG_PRINT(std::cerr << " OK!" << "\n");
 688           DEBUG_PRINT(std::cerr << "Node " << node->getNodeId() << " scheduled.\n");
 689         }
 690         //schedule[i][j]=node;
 691         while (schedule.size() <= i) {
 692           std::vector < ModuloSchedGraphNode * >*newCycle =
 693               new std::vector < ModuloSchedGraphNode * >();
 694           for (unsigned k = 0; k < numIssueSlots; k++)
 695             newCycle->push_back(NULL);
 696           schedule.push_back(*newCycle);
 697         }
 698         std::vector<ModuloSchedGraphNode*>::iterator startIterator;
 699         startIterator = schedule[i].begin();
 700         schedule[i].insert(startIterator + j, node);
 701         startIterator = schedule[i].begin();
 702         schedule[i].erase(startIterator + j + 1);
 703
 704         //update coreSchedule
 705         //coreSchedule[core_i][core_j]=node;
 706         while (coreSchedule.size() <= core_i) {
 707           std::vector<ModuloSchedGraphNode*> *newCycle =
 708               new std::vector<ModuloSchedGraphNode*>();
 709           for (unsigned k = 0; k < numIssueSlots; k++)
 710             newCycle->push_back(NULL);
 711           coreSchedule.push_back(*newCycle);
 712         }
 713
 714         startIterator = coreSchedule[core_i].begin();
 715         coreSchedule[core_i].insert(startIterator + core_j, node);
 716         startIterator = coreSchedule[core_i].begin();
 717         coreSchedule[core_i].erase(startIterator + core_j + 1);
 718
 719         node->setSchTime(i);
 720         isScheduled = true;
 721         nodeScheduled.push_back(node);
 722
 723         break;
 724       } else if (coreSchedule[core_i][core_j]) {
 725         if (ModuloScheduling::printScheduleProcess())
 726           DEBUG_PRINT(std::cerr << " Slot not available\n");
 727       } else {
 728         if (ModuloScheduling::printScheduleProcess())
 729           DEBUG_PRINT(std::cerr << " Resource conflicts\n");
 730       }
 731     }
 732     if (isScheduled)
 733       break;
 734   }
 735   //assert(nodeScheduled &&"this node can not be scheduled?");
 736   return isScheduled;
 737 }
 738
 739
 740 void
 741 ModuloScheduling::updateResourceTable(Resources useResources,
 742                                            int startCycle){
 743
 744   for (unsigned i = 0; i < useResources.size(); i++) {
 745     int absCycle = startCycle + i;
 746     int coreCycle = absCycle % II;
 747     std::vector<std::pair<int,int> > &resourceRemained =
 748         resourceTable[coreCycle];
 749     std::vector < unsigned int >&resourceUsed = useResources[i];
 750     for (unsigned j = 0; j < resourceUsed.size(); j++) {
 751       for (unsigned k = 0; k < resourceRemained.size(); k++)
 752         if ((int) resourceUsed[j] == resourceRemained[k].first) {
 753           resourceRemained[k].second--;
 754         }
 755     }
 756   }
 757 }
 758
 759 void
 760 ModuloScheduling::undoUpdateResourceTable(Resources useResources,
 761                                                int startCycle){
 762
 763   for (unsigned i = 0; i < useResources.size(); i++) {
 764     int absCycle = startCycle + i;
 765     int coreCycle = absCycle % II;
 766     std::vector<std::pair<int,int> > &resourceRemained =
 767         resourceTable[coreCycle];
 768     std::vector < unsigned int >&resourceUsed = useResources[i];
 769     for (unsigned j = 0; j < resourceUsed.size(); j++) {
 770       for (unsigned k = 0; k < resourceRemained.size(); k++)
 771         if ((int) resourceUsed[j] == resourceRemained[k].first) {
 772           resourceRemained[k].second++;
 773         }
 774     }
 775   }
 776 }
 777
 778
 779 //-----------------------------------------------------------------------
 780 // Function: resourceTableNegative
 781 // return value:
 782 //   return false if any element in the resouceTable is negative
 783 //   otherwise return true
 784 // Purpose:
 785
 786 //   this function is used to determine if an instruction is eligible for
 787 //   schedule at certain cycle
 788 //-----------------------------------------------------------------------
 789
 790
 791 bool
 792 ModuloScheduling::resourceTableNegative(){
 793
 794   assert(resourceTable.size() == (unsigned) II
 795          && "resouceTable size must be equal to II");
 796   bool isNegative = false;
 797   for (unsigned i = 0; i < resourceTable.size(); i++)
 798     for (unsigned j = 0; j < resourceTable[i].size(); j++) {
 799       if (resourceTable[i][j].second < 0) {
 800         isNegative = true;
 801         break;
 802       }
 803     }
 804   return isNegative;
 805 }
 806
 807
 808 //----------------------------------------------------------------------
 809 // Function: dumpResouceUsageTable
 810 // Purpose:
 811 //   print out ResouceTable for debug
 812 //
 813 //------------------------------------------------------------------------
 814
 815 void
 816 ModuloScheduling::dumpResourceUsageTable(){
 817
 818   DEBUG_PRINT(std::cerr << "dumping resource usage table\n");
 819   for (unsigned i = 0; i < resourceTable.size(); i++) {
 820     for (unsigned j = 0; j < resourceTable[i].size(); j++)
 821       DEBUG_PRINT(std::cerr << resourceTable[i][j].first
 822             << ":" << resourceTable[i][j].second << " ");
 823     DEBUG_PRINT(std::cerr << "\n");
 824   }
 825
 826 }
 827
 828 //----------------------------------------------------------------------
 829 //Function: dumpSchedule
 830 //Purpose:
 831 //       print out thisSchedule for debug
 832 //
 833 //-----------------------------------------------------------------------
 834 void
 835 ModuloScheduling::dumpSchedule(vvNodeType thisSchedule){
 836
 837   const TargetSchedInfo & msi = target.getSchedInfo();
 838   unsigned numIssueSlots = msi.maxNumIssueTotal;
 839   for (unsigned i = 0; i < numIssueSlots; i++)
 840     DEBUG_PRINT(std::cerr << "\t#");
 841   DEBUG_PRINT(std::cerr << "\n");
 842   for (unsigned i = 0; i < thisSchedule.size(); i++) {
 843     DEBUG_PRINT(std::cerr << "cycle" << i << ": ");
 844     for (unsigned j = 0; j < thisSchedule[i].size(); j++)
 845       if (thisSchedule[i][j] != NULL)
 846         DEBUG_PRINT(std::cerr << thisSchedule[i][j]->getNodeId() << "\t");
 847       else
 848         DEBUG_PRINT(std::cerr << "\t");
 849     DEBUG_PRINT(std::cerr << "\n");
 850   }
 851 }
 852
 853
 854 //----------------------------------------------------
 855 //Function: dumpScheduling
 856 //Purpose:
 857 //   print out the schedule and coreSchedule for debug
 858 //
 859 //-------------------------------------------------------
 860
 861 void
 862 ModuloScheduling::dumpScheduling(){
 863
 864   DEBUG_PRINT(std::cerr << "dump schedule:" << "\n");
 865   const TargetSchedInfo & msi = target.getSchedInfo();
 866   unsigned numIssueSlots = msi.maxNumIssueTotal;
 867   for (unsigned i = 0; i < numIssueSlots; i++)
 868     DEBUG_PRINT(std::cerr << "\t#");
 869   DEBUG_PRINT(std::cerr << "\n");
 870   for (unsigned i = 0; i < schedule.size(); i++) {
 871     DEBUG_PRINT(std::cerr << "cycle" << i << ": ");
 872     for (unsigned j = 0; j < schedule[i].size(); j++)
 873       if (schedule[i][j] != NULL)
 874         DEBUG_PRINT(std::cerr << schedule[i][j]->getNodeId() << "\t");
 875       else
 876         DEBUG_PRINT(std::cerr << "\t");
 877     DEBUG_PRINT(std::cerr << "\n");
 878   }
 879
 880   DEBUG_PRINT(std::cerr << "dump coreSchedule:" << "\n");
 881   for (unsigned i = 0; i < numIssueSlots; i++)
 882     DEBUG_PRINT(std::cerr << "\t#");
 883   DEBUG_PRINT(std::cerr << "\n");
 884   for (unsigned i = 0; i < coreSchedule.size(); i++) {
 885     DEBUG_PRINT(std::cerr << "cycle" << i << ": ");
 886     for (unsigned j = 0; j < coreSchedule[i].size(); j++)
 887       if (coreSchedule[i][j] != NULL)
 888         DEBUG_PRINT(std::cerr << coreSchedule[i][j]->getNodeId() << "\t");
 889       else
 890         DEBUG_PRINT(std::cerr << "\t");
 891     DEBUG_PRINT(std::cerr << "\n");
 892   }
 893 }
 894
 895 /*
 896   print out final schedule
 897 */
 898
 899 void
 900 ModuloScheduling::dumpFinalSchedule(){
 901
 902   std::cerr << "dump schedule:" << "\n";
 903   const TargetSchedInfo & msi = target.getSchedInfo();
 904   unsigned numIssueSlots = msi.maxNumIssueTotal;
 905
 906   for (unsigned i = 0; i < numIssueSlots; i++)
 907     std::cerr << "\t#";
 908   std::cerr << "\n";
 909
 910   for (unsigned i = 0; i < schedule.size(); i++) {
 911     std::cerr << "cycle" << i << ": ";
 912
 913     for (unsigned j = 0; j < schedule[i].size(); j++)
 914       if (schedule[i][j] != NULL)
 915         std::cerr << schedule[i][j]->getNodeId() << "\t";
 916       else
 917         std::cerr << "\t";
 918     std::cerr << "\n";
 919   }
 920
 921   std::cerr << "dump coreSchedule:" << "\n";
 922   for (unsigned i = 0; i < numIssueSlots; i++)
 923     std::cerr << "\t#";
 924   std::cerr << "\n";
 925
 926   for (unsigned i = 0; i < coreSchedule.size(); i++) {
 927     std::cerr << "cycle" << i << ": ";
 928     for (unsigned j = 0; j < coreSchedule[i].size(); j++)
 929       if (coreSchedule[i][j] != NULL)
 930         std::cerr << coreSchedule[i][j]->getNodeId() << "\t";
 931       else
 932         std::cerr << "\t";
 933     std::cerr << "\n";
 934   }
 935 }
 936
 937 //---------------------------------------------------------------------------
 938 // Function: ModuloSchedulingPass
 939 //
 940 // Purpose:
 941 //   Entry point for Modulo Scheduling
 942 //   Schedules LLVM instruction
 943 //
 944 //---------------------------------------------------------------------------
 945
 946 namespace {
 947   class ModuloSchedulingPass:public FunctionPass {
 948     const TargetMachine &target;
 949
 950   public:
 951     ModuloSchedulingPass(const TargetMachine &T):target(T) {}
 952
 953     const char *getPassName() const {
 954       return "Modulo Scheduling";
 955     }
 956
 957     // getAnalysisUsage - We use LiveVarInfo...
 958     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 959       //AU.addRequired(FunctionLiveVarInfo::ID);
 960     }
 961
 962     bool runOnFunction(Function & F);
 963   };
 964 }                               // end anonymous namespace
 965
 966
 967 bool
 968 ModuloSchedulingPass::runOnFunction(Function &F){
 969
 970   ModuloSchedGraphSet *graphSet = new ModuloSchedGraphSet(&F, target);
 971
 972   ModuloSchedulingSet ModuloSchedulingSet(*graphSet);
 973
 974   DEBUG_PRINT(std::cerr<<"runOnFunction  in ModuloSchedulingPass returns\n"<<"\n");
 975   return false;
 976 }
 977
 978
 979 Pass *
 980 createModuloSchedulingPass(const TargetMachine & tgt){
 981   DEBUG_PRINT(std::cerr<<"creating modulo scheduling\n");
 982   return new ModuloSchedulingPass(tgt);
 983 }