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