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