*** empty log message ***
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5755 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp b/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp
new file mode 100644
index 0000000..3f4002a
--- /dev/null
+++ b/lib/CodeGen/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);
+}
+