lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp

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