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