diff options
Diffstat (limited to 'lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp')
| -rw-r--r-- | lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp | 899 |
1 files changed, 899 insertions, 0 deletions
diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp new file mode 100644 index 0000000000..3f4002abe2 --- /dev/null +++ b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp @@ -0,0 +1,899 @@ + +//===- SPLInstrScheduling.cpp - Modulo Software Pipelining Instruction Scheduling support -------===// +// +// this file implements the llvm/CodeGen/ModuloScheduling.h interface +// +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineCodeForInstruction.h" +#include "llvm/CodeGen/MachineCodeForBasicBlock.h" +#include "llvm/CodeGen/MachineCodeForMethod.h" +#include "llvm/Analysis/LiveVar/FunctionLiveVarInfo.h" // FIXME: Remove when modularized better +#include "llvm/Target/TargetMachine.h" +#include "llvm/BasicBlock.h" +#include "llvm/Instruction.h" +#include "Support/CommandLine.h" +#include <algorithm> +#include "ModuloSchedGraph.h" +#include "ModuloScheduling.h" +#include "llvm/Target/MachineSchedInfo.h" +#include "llvm/BasicBlock.h" +#include "llvm/iTerminators.h" +#include "llvm/iPHINode.h" +#include "llvm/Constants.h" +#include <iostream> +#include <swig.h> +#include <fstream> +#include "llvm/CodeGen/InstrSelection.h" + +#define max(x,y) (x>y?x:y) +#define min(x,y) (x<y?x:y) +using std::cerr; +using std::cout; +using std::ostream; +using std::ios; +using std::filebuf; + +//************************************************************ +//printing Debug information +//ModuloSchedDebugLevel stores the value of debug level +// modsched_os is the ostream to dump debug information, which is written into the file 'moduloSchedDebugInfo.output' +//see ModuloSchedulingPass::runOnFunction() +//************************************************************ + +ModuloSchedDebugLevel_t ModuloSchedDebugLevel; +static cl::opt<ModuloSchedDebugLevel_t, true> +SDL_opt("modsched", cl::Hidden, cl::location(ModuloSchedDebugLevel), + cl::desc("enable modulo scheduling debugging information"), + cl::values( + clEnumValN(ModuloSched_NoDebugInfo, "n", "disable debug output"), + clEnumValN(ModuloSched_Disable, "off", "disable modulo scheduling"), + clEnumValN(ModuloSched_PrintSchedule, "psched", "print original and new schedule"), + clEnumValN(ModuloSched_PrintScheduleProcess,"pschedproc", "print how the new schdule is produced"), + 0)); + +filebuf modSched_fb; +ostream modSched_os(&modSched_fb); + +//************************************************************ + + +///the method to compute schedule and instert epilogue and prologue +void ModuloScheduling::instrScheduling(){ + + if( ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess) + modSched_os<<"*************************computing modulo schedule ************************\n"; + + + const MachineSchedInfo& msi=target.getSchedInfo(); + + //number of issue slots in the in each cycle + int numIssueSlots=msi.maxNumIssueTotal; + + + + //compute the schedule + bool success=false; + while(!success) + { + //clear memory from the last round and initialize if necessary + clearInitMem(msi); + + //compute schedule and coreSchedule with the current II + success=computeSchedule(); + + if(!success){ + II++; + if( ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess) + modSched_os<<"increase II to "<<II<<"\n"; + } + } + + //print the final schedule if necessary + if( ModuloSchedDebugLevel >= ModuloSched_PrintSchedule) + dumpScheduling(); + + + //the schedule has been computed + //create epilogue, prologue and kernel BasicBlock + + //find the successor for this BasicBlock + BasicBlock* succ_bb= getSuccBB(bb); + + //print the original BasicBlock if necessary + if( ModuloSchedDebugLevel >= ModuloSched_PrintSchedule){ + modSched_os<<"dumping the orginal block\n"; + graph.dump(bb); + } + + //construction of prologue, kernel and epilogue + BasicBlock* kernel=bb->splitBasicBlock(bb->begin()); + BasicBlock* prologue= bb; + BasicBlock* epilogue=kernel->splitBasicBlock(kernel->begin()); + + + //construct prologue + constructPrologue(prologue); + + //construct kernel + constructKernel(prologue,kernel,epilogue); + + //construct epilogue + constructEpilogue(epilogue,succ_bb); + + + //print the BasicBlocks if necessary + if( ModuloSchedDebugLevel >= ModuloSched_PrintSchedule){ + modSched_os<<"dumping the prologue block:\n"; + graph.dump(prologue); + modSched_os<<"dumping the kernel block\n"; + graph.dump(kernel); + modSched_os<<"dumping the epilogue block\n"; + graph.dump(epilogue); + } + +} + +//clear memory from the last round and initialize if necessary +void ModuloScheduling::clearInitMem(const MachineSchedInfo& msi){ + + + unsigned numIssueSlots = msi.maxNumIssueTotal; + //clear nodeScheduled from the last round + if( ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess){ + modSched_os<< "***** new round with II= "<<II<<" *******************"<<endl; + modSched_os<< " **************clear the vector nodeScheduled**************** \n"; + } + nodeScheduled.clear(); + + + //clear resourceTable from the last round and reset it + resourceTable.clear(); + for(unsigned i=0;i< II;i++) + resourceTable.push_back(msi.resourceNumVector); + + + //clear the schdule and coreSchedule from the last round + schedule.clear(); + coreSchedule.clear(); + + //create a coreSchedule of size II*numIssueSlots + //each entry is NULL + while( coreSchedule.size() < II){ + std::vector<ModuloSchedGraphNode*>* newCycle=new std::vector<ModuloSchedGraphNode*>(); + for(unsigned k=0;k<numIssueSlots;k++) + newCycle->push_back(NULL); + coreSchedule.push_back(*newCycle); + } +} + + +//compute schedule and coreSchedule with the current II +bool ModuloScheduling::computeSchedule(){ + + if( ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess) + modSched_os <<"start to compute schedule \n"; + + //loop over the ordered nodes + for(NodeVec::const_iterator I=oNodes.begin();I!=oNodes.end();I++) + { + //try to schedule for node I + if( ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess) + dumpScheduling(); + ModuloSchedGraphNode* node=*I; + + //compute whether this node has successor(s) + bool succ=true; + + //compute whether this node has predessor(s) + bool pred=true; + + NodeVec schSucc=graph.vectorConj(nodeScheduled,graph.succSet(node)); + if(schSucc.empty()) + succ=false; + NodeVec schPred=graph.vectorConj(nodeScheduled,graph.predSet(node)); + if(schPred.empty()) + pred=false; + + //startTime: the earliest time we will try to schedule this node + //endTime: the latest time we will try to schedule this node + int startTime, endTime; + + //node's earlyStart: possible earliest time to schedule this node + //node's lateStart: possible latest time to schedule this node + node->setEarlyStart(-1); + node->setLateStart(9999); + + + //this node has predessor but no successor + if(!succ && pred){ + + //this node's earlyStart is it's predessor's schedule time + the edge delay + // - the iteration difference* II + for(unsigned i=0;i<schPred.size();i++){ + ModuloSchedGraphNode* predNode=schPred[i]; + SchedGraphEdge* edge=graph.getMaxDelayEdge(predNode->getNodeId(),node->getNodeId()); + int temp=predNode->getSchTime()+edge->getMinDelay() - edge->getIteDiff()*II; + node->setEarlyStart( max(node->getEarlyStart(),temp)); + } + startTime=node->getEarlyStart(); + endTime=node->getEarlyStart()+II-1; + } + + + //this node has successor but no predessor + if(succ && !pred){ + for(unsigned i=0;i<schSucc.size();i++){ + ModuloSchedGraphNode* succNode=schSucc[i]; + SchedGraphEdge* edge=graph.getMaxDelayEdge(succNode->getNodeId(),node->getNodeId()); + int temp=succNode->getSchTime() - edge->getMinDelay() + edge->getIteDiff()*II; + node->setLateStart(min(node->getEarlyStart(),temp)); + } + startTime=node->getLateStart()- II+1; + endTime=node->getLateStart(); + } + + //this node has both successors and predessors + if(succ && pred) + { + for(unsigned i=0;i<schPred.size();i++){ + ModuloSchedGraphNode* predNode=schPred[i]; + SchedGraphEdge* edge=graph.getMaxDelayEdge(predNode->getNodeId(),node->getNodeId()); + int temp=predNode->getSchTime()+edge->getMinDelay() - edge->getIteDiff()*II; + node->setEarlyStart(max(node->getEarlyStart(),temp)); + } + for(unsigned i=0;i<schSucc.size();i++){ + ModuloSchedGraphNode* succNode=schSucc[i]; + SchedGraphEdge* edge=graph.getMaxDelayEdge(succNode->getNodeId(),node->getNodeId()); + int temp=succNode->getSchTime() - edge->getMinDelay() + edge->getIteDiff()*II; + node->setLateStart(min(node->getEarlyStart(),temp)); + } + startTime=node->getEarlyStart(); + endTime=min(node->getLateStart(),node->getEarlyStart()+((int)II)-1); + } + + //this node has no successor or predessor + if(!succ && !pred){ + node->setEarlyStart(node->getASAP()); + startTime=node->getEarlyStart(); + endTime=node->getEarlyStart()+II -1; + } + + //try to schedule this node based on the startTime and endTime + if( ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess) + modSched_os<<"scheduling the node "<<(*I)->getNodeId()<<"\n"; + + bool success= this->ScheduleNode(node,startTime, endTime,nodeScheduled); + if(!success)return false; + } + return true; +} + + +//get the successor of the BasicBlock +BasicBlock* ModuloScheduling::getSuccBB(BasicBlock* bb){ + + BasicBlock* succ_bb; + for(unsigned i=0;i < II; i++) + for(unsigned j=0;j< coreSchedule[i].size();j++) + if(coreSchedule[i][j]){ + const Instruction* ist=coreSchedule[i][j]->getInst(); + + //we can get successor from the BranchInst instruction + //assume we only have one successor (besides itself) here + if(BranchInst::classof(ist)){ + BranchInst* bi=(BranchInst*)ist; + assert(bi->isConditional()&&"the branchInst is not a conditional one"); + assert(bi->getNumSuccessors() ==2&&" more than two successors?"); + BasicBlock* bb1=bi->getSuccessor(0); + BasicBlock* bb2=bi->getSuccessor(1); + assert( (bb1 == bb|| bb2 == bb) && " None of its successor is itself?"); + if(bb1 == bb) succ_bb=bb2; + else succ_bb=bb1; + return succ_bb; + } + } + assert( 0 && "NO Successor?"); + return NULL; +} + + +//get the predecessor of the BasicBlock +BasicBlock* ModuloScheduling::getPredBB(BasicBlock* bb){ + + BasicBlock* pred_bb; + + for(unsigned i=0;i < II; i++) + for(unsigned j=0;j< coreSchedule[i].size();j++) + if(coreSchedule[i][j]){ + const Instruction* ist=coreSchedule[i][j]->getInst(); + + //we can get predecessor from the PHINode instruction + //assume we only have one predecessor (besides itself) here + if(PHINode::classof(ist)){ + PHINode* phi=(PHINode*) ist; + assert(phi->getNumIncomingValues() == 2 &&" the number of incoming value is not equal to two? "); + BasicBlock* bb1= phi->getIncomingBlock(0); + BasicBlock* bb2= phi->getIncomingBlock(1); + assert( (bb1 == bb || bb2 == bb) && " None of its predecessor is itself?"); + if(bb1 == bb) pred_bb=bb2; + else pred_bb=bb1; + return pred_bb; + } + } + assert(0 && " no predecessor?"); + return NULL; +} + + +//construct the prologue +void ModuloScheduling::constructPrologue(BasicBlock* prologue){ + + InstListType& prologue_ist = prologue->getInstList(); + vvNodeType& tempSchedule_prologue= *(new vector< std::vector<ModuloSchedGraphNode*> >(schedule)); + + //compute the schedule for prologue + unsigned round=0; + unsigned scheduleSize=schedule.size(); + while(round < scheduleSize/II){ + round++; + for(unsigned i=0;i < scheduleSize ;i++){ + if(round*II + i >= scheduleSize) break; + for(unsigned j=0;j < schedule[i].size(); j++) + if(schedule[i][j]){ + assert( tempSchedule_prologue[round*II +i ][j] == NULL && "table not consitant with core table"); + + //move the schedule one iteration ahead and overlap with the original one + tempSchedule_prologue[round*II + i][j]=schedule[i][j]; + } + } + } + + //clear the clone memory in the core schedule instructions + clearCloneMemory(); + + //fill in the prologue + for(unsigned i=0;i < ceil(1.0*scheduleSize/II -1)*II ;i++) + for(unsigned j=0;j < tempSchedule_prologue[i].size();j++) + if(tempSchedule_prologue[i][j]){ + + //get the instruction + Instruction* orn=(Instruction*)tempSchedule_prologue[i][j]->getInst(); + + //made a clone of it + Instruction* cln=cloneInstSetMemory(orn); + + //insert the instruction + prologue_ist.insert(prologue_ist.back(),cln ); + + //if there is PHINode in the prologue, the incoming value from itself should be removed + //because it is not a loop any longer + if( PHINode::classof(cln)){ + PHINode* phi=(PHINode*)cln; + phi->removeIncomingValue(phi->getParent()); + } + } +} + + +//construct the kernel BasicBlock +void ModuloScheduling::constructKernel(BasicBlock* prologue,BasicBlock* kernel,BasicBlock* epilogue){ + + //*************fill instructions in the kernel**************** + InstListType& kernel_ist = kernel->getInstList(); + BranchInst* brchInst; + PHINode* phiInst, *phiCln; + + for(unsigned i=0;i<coreSchedule.size();i++) + for(unsigned j=0;j<coreSchedule[i].size();j++) + if(coreSchedule[i][j]){ + + //we should take care of branch instruction differently with normal instructions + if(BranchInst::classof(coreSchedule[i][j]->getInst())){ + brchInst=(BranchInst*)coreSchedule[i][j]->getInst(); + continue; + } + + //we should take care of PHINode instruction differently with normal instructions + if( PHINode::classof(coreSchedule[i][j]->getInst())){ + phiInst= (PHINode*)coreSchedule[i][j]->getInst(); + Instruction* cln=cloneInstSetMemory(phiInst); + kernel_ist.insert(kernel_ist.back(),cln); + phiCln=(PHINode*)cln; + continue; + } + + //for normal instructions: made a clone and insert it in the kernel_ist + Instruction* cln=cloneInstSetMemory( (Instruction*)coreSchedule[i][j]->getInst()); + kernel_ist.insert(kernel_ist.back(),cln); + } + + //the two incoming BasicBlock for PHINode is the prologue and the kernel (itself) + phiCln->setIncomingBlock(0,prologue); + phiCln->setIncomingBlock(1,kernel); + + //the incoming value for the kernel (itself) is the new value which is computed in the kernel + Instruction* originalVal=(Instruction*)phiInst->getIncomingValue(1); + phiCln->setIncomingValue(1, originalVal->getClone()); + + + //make a clone of the branch instruction and insert it in the end + BranchInst* cln=(BranchInst*)cloneInstSetMemory( brchInst); + kernel_ist.insert(kernel_ist.back(),cln); + + //delete the unconditional branch instruction, which is generated when splitting the basicBlock + kernel_ist.erase( --kernel_ist.end()); + + //set the first successor to itself + ((BranchInst*)cln)->setSuccessor(0, kernel); + //set the second successor to eiplogue + ((BranchInst*)cln)->setSuccessor(1,epilogue); + + //*****change the condition******* + + //get the condition instruction + Instruction* cond=(Instruction*)cln->getCondition(); + + //get the condition's second operand, it should be a constant + Value* operand=cond->getOperand(1); + assert(ConstantSInt::classof(operand)); + + //change the constant in the condtion instruction + ConstantSInt* iteTimes=ConstantSInt::get(operand->getType(),((ConstantSInt*)operand)->getValue()-II+1); + cond->setOperand(1,iteTimes); + +} + + + + + +//construct the epilogue +void ModuloScheduling::constructEpilogue(BasicBlock* epilogue, BasicBlock* succ_bb){ + + //compute the schedule for epilogue + vvNodeType& tempSchedule_epilogue= *(new vector< std::vector<ModuloSchedGraphNode*> >(schedule)); + unsigned scheduleSize=schedule.size(); + int round =0; + while(round < ceil(1.0*scheduleSize/II )-1 ){ + round++; + for( unsigned i=0;i < scheduleSize ; i++){ + if(i + round *II >= scheduleSize) break; + for(unsigned j=0;j < schedule[i].size();j++) + if(schedule[i + round*II ][j]){ + assert( tempSchedule_epilogue[i][j] == NULL && "table not consitant with core table"); + + //move the schdule one iteration behind and overlap + tempSchedule_epilogue[i][j]=schedule[i + round*II][j]; + } + } + } + + //fill in the epilogue + InstListType& epilogue_ist = epilogue->getInstList(); + for(unsigned i=II;i <scheduleSize ;i++) + for(unsigned j=0;j < tempSchedule_epilogue[i].size();j++) + if(tempSchedule_epilogue[i][j]){ + Instruction* inst=(Instruction*)tempSchedule_epilogue[i][j]->getInst(); + + //BranchInst and PHINode should be treated differently + //BranchInst:unecessary, simly omitted + //PHINode: omitted + if( !BranchInst::classof(inst) && ! PHINode::classof(inst) ){ + //make a clone instruction and insert it into the epilogue + Instruction* cln=cloneInstSetMemory(inst); + epilogue_ist.push_front(cln); + } + } + + + //*************delete the original instructions****************// + //to delete the original instructions, we have to make sure their use is zero + + //update original core instruction's uses, using its clone instread + for(unsigned i=0;i < II; i++) + for(unsigned j=0;j < coreSchedule[i].size() ;j++){ + if(coreSchedule[i][j]) + updateUseWithClone((Instruction*)coreSchedule[i][j]->getInst() ); + } + + //erase these instructions + for(unsigned i=0;i < II; i++) + for(unsigned j=0;j < coreSchedule[i].size();j++) + if(coreSchedule[i][j]){ + Instruction* ist=(Instruction*)coreSchedule[i][j]->getInst(); + ist->getParent()->getInstList().erase(ist); + } + //**************************************************************// + + + //finally, insert an unconditional branch instruction at the end + epilogue_ist.push_back(new BranchInst(succ_bb)); + +} + + +//---------------------------------------------------------------------------------------------- +//this function replace the value(instruction) ist in other instructions with its latest clone +//i.e. after this function is called, the ist is not used anywhere and it can be erased. +//---------------------------------------------------------------------------------------------- +void ModuloScheduling::updateUseWithClone(Instruction* ist){ + + while(ist->use_size() >0){ + bool destroyed=false; + + //other instruction is using this value ist + assert(Instruction::classof(*ist->use_begin())); + Instruction *inst=(Instruction*)(* ist->use_begin()); + + for(unsigned i=0;i<inst->getNumOperands();i++) + if(inst->getOperand(i) == ist && ist->getClone()){ + + //if the instruction is TmpInstruction, simly delete it because it has no parent + // and it does not belongs to any BasicBlock + if(TmpInstruction::classof(inst)) { + delete inst; + destroyed=true; + break; + } + + + //otherwise, set the instruction's operand to the value's clone + inst->setOperand(i, ist->getClone()); + + //the use from the original value ist is destroyed + destroyed=true; + break; + } + if( !destroyed) + { + //if the use can not be destroyed , something is wrong + inst->dump(); + assert( 0 &&"this use can not be destroyed"); + } + } + +} + + +//******************************************************** +//this function clear all clone mememoy +//i.e. set all instruction's clone memory to NULL +//***************************************************** +void ModuloScheduling::clearCloneMemory(){ +for(unsigned i=0; i < coreSchedule.size();i++) + for(unsigned j=0;j<coreSchedule[i].size();j++) + if(coreSchedule[i][j]) ((Instruction*)coreSchedule[i][j]->getInst())->clearClone(); + +} + + +//******************************************************************************** +//this function make a clone of the instruction orn +//the cloned instruction will use the orn's operands' latest clone as its operands +//it is done this way because LLVM is in SSA form and we should use the correct value +// +//this fuction also update the instruction orn's latest clone memory +//********************************************************************************** +Instruction* ModuloScheduling::cloneInstSetMemory(Instruction* orn) { + +//make a clone instruction + Instruction* cln=orn->clone(); + + + //update the operands + for(unsigned k=0;k<orn->getNumOperands();k++){ + const Value* op=orn->getOperand(k); + if(Instruction::classof(op) && ((Instruction*)op)->getClone()){ + Instruction* op_inst=(Instruction*)op; + cln->setOperand(k, op_inst->getClone()); + } + } + + //update clone memory + orn->setClone(cln); + return cln; +} + + + +bool ModuloScheduling::ScheduleNode(ModuloSchedGraphNode* node,unsigned start, unsigned end, NodeVec& nodeScheduled) +{ + + const MachineSchedInfo& msi=target.getSchedInfo(); + unsigned int numIssueSlots=msi.maxNumIssueTotal; + + if( ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess) + modSched_os<<"startTime= "<<start<<" endTime= "<<end<<"\n"; + bool isScheduled=false; + for(unsigned i=start;i<= end;i++){ + if( ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess) + modSched_os<< " now try cycle " <<i<<":"<<"\n"; + for(unsigned j=0;j<numIssueSlots;j++){ + unsigned int core_i = i%II; + unsigned int core_j=j; + if( ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess) + modSched_os <<"\t Trying slot "<<j<<"..........."; + //check the resouce table, make sure there is no resource conflicts + const Instruction* instr=node->getInst(); + MachineCodeForInstruction& tempMvec= MachineCodeForInstruction::get(instr); + bool resourceConflict=false; + const MachineInstrInfo &mii=msi.getInstrInfo(); + + if(coreSchedule.size() < core_i+1 || !coreSchedule[core_i][core_j]){ + //this->dumpResourceUsageTable(); + int latency=0; + for(unsigned k=0;k< tempMvec.size();k++) + { + MachineInstr* minstr=tempMvec[k]; + InstrRUsage rUsage=msi.getInstrRUsage(minstr->getOpCode()); + std::vector<std::vector<resourceId_t> > resources + =rUsage.resourcesByCycle; + updateResourceTable(resources,i + latency); + latency +=max(mii.minLatency(minstr->getOpCode()),1) ; + } + + //this->dumpResourceUsageTable(); + + latency=0; + if( resourceTableNegative()){ + + //undo-update the resource table + for(unsigned k=0;k< tempMvec.size();k++){ + MachineInstr* minstr=tempMvec[k]; + InstrRUsage rUsage=msi.getInstrRUsage(minstr->getOpCode()); + std::vector<std::vector<resourceId_t> > resources + =rUsage.resourcesByCycle; + undoUpdateResourceTable(resources,i + latency); + latency +=max(mii.minLatency(minstr->getOpCode()),1) ; + } + resourceConflict=true; + } + } + if( !resourceConflict && !coreSchedule[core_i][core_j]){ + if( ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess){ + modSched_os <<" OK!"<<"\n"; + modSched_os<<"Node "<<node->getNodeId()<< " is scheduleed."<<"\n"; + } + //schedule[i][j]=node; + while(schedule.size() <= i){ + std::vector<ModuloSchedGraphNode*>* newCycle=new std::vector<ModuloSchedGraphNode*>(); + for(unsigned k=0;k<numIssueSlots;k++) + newCycle->push_back(NULL); + schedule.push_back(*newCycle); + } + vector<ModuloSchedGraphNode*>::iterator startIterator; + startIterator = schedule[i].begin(); + schedule[i].insert(startIterator+j,node); + startIterator = schedule[i].begin(); + schedule[i].erase(startIterator+j+1); + + //update coreSchedule + //coreSchedule[core_i][core_j]=node; + while(coreSchedule.size() <= core_i){ + std::vector<ModuloSchedGraphNode*>* newCycle=new std::vector<ModuloSchedGraphNode*>(); + for(unsigned k=0;k<numIssueSlots;k++) + newCycle->push_back(NULL); + coreSchedule.push_back(*newCycle); + } + + startIterator = coreSchedule[core_i].begin(); + coreSchedule[core_i].insert(startIterator+core_j,node); + startIterator = coreSchedule[core_i].begin(); + coreSchedule[core_i].erase(startIterator+core_j+1); + + node->setSchTime(i); + isScheduled=true; + nodeScheduled.push_back(node); + + break; + } + else if( coreSchedule[core_i][core_j]) { + if( ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess) + modSched_os <<" Slot not available "<<"\n"; + } + else{ + if( ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess) + modSched_os <<" Resource conflicts"<<"\n"; + } + } + if(isScheduled) break; + } + //assert(nodeScheduled &&"this node can not be scheduled?"); + return isScheduled; +} + +void ModuloScheduling::updateResourceTable(std::vector<std::vector<unsigned int> > useResources, int startCycle){ + for(unsigned i=0;i< useResources.size();i++){ + int absCycle=startCycle+i; + int coreCycle=absCycle % II; + std::vector<pair<int,int> >& resourceRemained=resourceTable[coreCycle]; + std::vector<unsigned int>& resourceUsed= useResources[i]; + for(unsigned j=0;j< resourceUsed.size();j++){ + for(unsigned k=0;k< resourceRemained.size();k++) + if((int)resourceUsed[j] == resourceRemained[k].first){ + resourceRemained[k].second--; + } + } + } +} + +void ModuloScheduling::undoUpdateResourceTable(std::vector<std::vector<unsigned int> > useResources, int startCycle){ + for(unsigned i=0;i< useResources.size();i++){ + int absCycle=startCycle+i; + int coreCycle=absCycle % II; + std::vector<pair<int,int> >& resourceRemained=resourceTable[coreCycle]; + std::vector<unsigned int>& resourceUsed= useResources[i]; + for(unsigned j=0;j< resourceUsed.size();j++){ + for(unsigned k=0;k< resourceRemained.size();k++) + if((int)resourceUsed[j] == resourceRemained[k].first){ + resourceRemained[k].second++; + } + } + } +} + + +//----------------------------------------------------------------------- +//Function: resouceTableNegative +//return value: +// return false if any element in the resouceTable is negative +// otherwise return true +//Purpose: +// this function is used to determine if an instruction is eligible for schedule at certain cycle +//--------------------------------------------------------------------------------------- + +bool ModuloScheduling::resourceTableNegative(){ + assert(resourceTable.size() == (unsigned)II&& "resouceTable size must be equal to II"); + bool isNegative=false; + for(unsigned i=0; i < resourceTable.size();i++) + for(unsigned j=0;j < resourceTable[i].size();j++){ + if(resourceTable[i][j].second <0) { + isNegative=true; + break; + } + } + return isNegative; +} + + +//---------------------------------------------------------------------- +//Function: dumpResouceUsageTable +//Purpose: +// print out ResouceTable for debug +// +//------------------------------------------------------------------------ + +void ModuloScheduling::dumpResourceUsageTable(){ + modSched_os<<"dumping resource usage table"<<"\n"; + for(unsigned i=0;i< resourceTable.size();i++){ + for(unsigned j=0;j < resourceTable[i].size();j++) + modSched_os <<resourceTable[i][j].first<<":"<< resourceTable[i][j].second<<" "; + modSched_os <<"\n"; + } + +} + +//---------------------------------------------------------------------- +//Function: dumpSchedule +//Purpose: +// print out thisSchedule for debug +// +//----------------------------------------------------------------------- +void ModuloScheduling::dumpSchedule(std::vector< std::vector<ModuloSchedGraphNode*> > thisSchedule){ + + const MachineSchedInfo& msi=target.getSchedInfo(); + unsigned numIssueSlots=msi.maxNumIssueTotal; + for(unsigned i=0;i< numIssueSlots;i++) + modSched_os <<"\t#"; + modSched_os<<"\n"; + for(unsigned i=0;i < thisSchedule.size();i++) + { + modSched_os<<"cycle"<<i<<": "; + for(unsigned j=0;j<thisSchedule[i].size();j++) + if(thisSchedule[i][j]!= NULL) + modSched_os<<thisSchedule[i][j]->getNodeId()<<"\t"; + else + modSched_os<<"\t"; + modSched_os<<"\n"; + } + +} + + +//---------------------------------------------------- +//Function: dumpScheduling +//Purpose: +// print out the schedule and coreSchedule for debug +// +//------------------------------------------------------- + +void ModuloScheduling::dumpScheduling(){ + modSched_os<<"dump schedule:"<<"\n"; + const MachineSchedInfo& msi=target.getSchedInfo(); + unsigned numIssueSlots=msi.maxNumIssueTotal; + for(unsigned i=0;i< numIssueSlots;i++) + modSched_os <<"\t#"; + modSched_os<<"\n"; + for(unsigned i=0;i < schedule.size();i++) + { + modSched_os<<"cycle"<<i<<": "; + for(unsigned j=0;j<schedule[i].size();j++) + if(schedule[i][j]!= NULL) + modSched_os<<schedule[i][j]->getNodeId()<<"\t"; + else + modSched_os<<"\t"; + modSched_os<<"\n"; + } + + modSched_os<<"dump coreSchedule:"<<"\n"; + for(unsigned i=0;i< numIssueSlots;i++) + modSched_os <<"\t#"; + modSched_os<<"\n"; + for(unsigned i=0;i < coreSchedule.size();i++){ + modSched_os<<"cycle"<<i<<": "; + for(unsigned j=0;j< coreSchedule[i].size();j++) + if(coreSchedule[i][j] !=NULL) + modSched_os<<coreSchedule[i][j]->getNodeId()<<"\t"; + else + modSched_os<<"\t"; + modSched_os<<"\n"; + } +} + + + +//--------------------------------------------------------------------------- +// Function: ModuloSchedulingPass +// +// Purpose: +// Entry point for Modulo Scheduling +// Schedules LLVM instruction +// +//--------------------------------------------------------------------------- + +namespace { + class ModuloSchedulingPass : public FunctionPass { + const TargetMachine ⌖ + public: + ModuloSchedulingPass(const TargetMachine &T) : target(T) {} + const char *getPassName() const { return "Modulo Scheduling"; } + + // getAnalysisUsage - We use LiveVarInfo... + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + //AU.addRequired(FunctionLiveVarInfo::ID); + } + bool runOnFunction(Function &F); + }; +} // end anonymous namespace + + + +bool ModuloSchedulingPass::runOnFunction(Function &F) +{ + + //if necessary , open the output for debug purpose + if(ModuloSchedDebugLevel== ModuloSched_Disable) + return false; + + if(ModuloSchedDebugLevel>= ModuloSched_PrintSchedule){ + modSched_fb.open("moduloSchedDebugInfo.output", ios::out); + modSched_os<<"******************Modula Scheduling debug information*************************"<<endl; + } + + ModuloSchedGraphSet* graphSet = new ModuloSchedGraphSet(&F,target); + ModuloSchedulingSet ModuloSchedulingSet(*graphSet); + + if(ModuloSchedDebugLevel>= ModuloSched_PrintSchedule) + modSched_fb.close(); + + return false; +} + + +Pass *createModuloSchedulingPass(const TargetMachine &tgt) { + return new ModuloSchedulingPass(tgt); +} + |