diff options
Diffstat (limited to 'lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp')
| -rw-r--r-- | lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp | 1359 |
1 files changed, 698 insertions, 661 deletions
diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp index 08cea9dce9..84ce1cd070 100644 --- a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp @@ -1,561 +1,580 @@ - -//===- SPLInstrScheduling.cpp - Modulo Software Pipelining Instruction Scheduling support -------===// -// -// this file implements the llvm/CodeGen/ModuloScheduling.h interface +//===- ModuloScheduling.cpp - Modulo Software Pipelining ------------------===// // +// 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/CodeGen/MachineFunction.h" //#include "llvm/Analysis/LiveVar/FunctionLiveVarInfo.h" // FIXME: Remove when modularized better -#include "llvm/Target/TargetMachine.h" #include "llvm/BasicBlock.h" +#include "llvm/Constants.h" #include "llvm/Instruction.h" +#include "llvm/iTerminators.h" +#include "llvm/iPHINode.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineCodeForInstruction.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/InstrSelection.h" +#include "llvm/Target/TargetSchedInfo.h" +#include "llvm/Target/TargetMachine.h" #include "Support/CommandLine.h" -#include <algorithm> #include "ModuloSchedGraph.h" #include "ModuloScheduling.h" -#include "llvm/Target/TargetSchedInfo.h" -#include "llvm/BasicBlock.h" -#include "llvm/iTerminators.h" -#include "llvm/iPHINode.h" -#include "llvm/Constants.h" +#include <algorithm> +#include <fstream> #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() +// 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> +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); - -//************************************************************ + 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)); + +std::filebuf modSched_fb; +std::ostream modSched_os(&modSched_fb); + +// Computes the schedule and inserts epilogue and prologue +// +void ModuloScheduling::instrScheduling() +{ + if (ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess) + modSched_os << "*************** computing modulo schedule **************\n"; -///the method to compute schedule and instert epilogue and prologue -void ModuloScheduling::instrScheduling(){ - - if( ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess) - modSched_os<<"*************************computing modulo schedule ************************\n"; - - - const TargetSchedInfo& msi=target.getSchedInfo(); + const TargetSchedInfo & msi = target.getSchedInfo(); //number of issue slots in the in each cycle - int numIssueSlots=msi.maxNumIssueTotal; - - + 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"; - } + 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) + 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); - + BasicBlock *succ_bb = getSuccBB(bb); + //print the original BasicBlock if necessary - if( ModuloSchedDebugLevel >= ModuloSched_PrintSchedule){ - modSched_os<<"dumping the orginal block\n"; + 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 + 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 kernel + constructKernel(prologue, kernel, epilogue); - //construct epilogue - constructEpilogue(epilogue,succ_bb); + // Construct epilogue + constructEpilogue(epilogue, succ_bb); - //print the BasicBlocks if necessary - if( ModuloSchedDebugLevel >= ModuloSched_PrintSchedule){ - modSched_os<<"dumping the prologue block:\n"; + if (ModuloSchedDebugLevel >= ModuloSched_PrintSchedule) { + modSched_os << "dumping the prologue block:\n"; graph.dump(prologue); - modSched_os<<"dumping the kernel block\n"; + modSched_os << "dumping the kernel block\n"; graph.dump(kernel); - modSched_os<<"dumping the epilogue block\n"; + modSched_os << "dumping the epilogue block\n"; graph.dump(epilogue); } - -} - -//clear memory from the last round and initialize if necessary -void ModuloScheduling::clearInitMem(const TargetSchedInfo& msi){ - +} +// Clear memory from the last round and initialize if necessary +// +void ModuloScheduling::clearInitMem(const TargetSchedInfo & msi) +{ unsigned numIssueSlots = msi.maxNumIssueTotal; - //clear nodeScheduled from the last round - if( ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess){ - modSched_os<< "***** new round with II= "<<II<<" *******************"<<"\n"; - modSched_os<< " **************clear the vector nodeScheduled**************** \n"; + // clear nodeScheduled from the last round + if (ModuloSchedDebugLevel >= ModuloSched_PrintScheduleProcess) { + modSched_os << "***** new round with II= " << II << + " *******************\n"; + modSched_os << + " ************clear the vector nodeScheduled*************\n"; } nodeScheduled.clear(); - - - //clear resourceTable from the last round and reset it + + // clear resourceTable from the last round and reset it resourceTable.clear(); - for(unsigned i=0;i< II;i++) + for (unsigned i = 0; i < II; ++i) resourceTable.push_back(msi.resourceNumVector); - - - //clear the schdule and coreSchedule from the last round + + // 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++) + + // 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() +{ -//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; + 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(std::max(node->getEarlyStart(), temp)); } - - - //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(); + startTime = node->getEarlyStart(); + endTime = node->getEarlyStart() + II - 1; + } + // This node has a successor but no predecessor + 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(std::min(node->getEarlyStart(), temp)); } - - //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; + startTime = node->getLateStart() - II + 1; + endTime = node->getLateStart(); + } + // This node has both successors and predecessors + 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(std::max(node->getEarlyStart(), temp)); } - - //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; + 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(std::min(node->getEarlyStart(), temp)); + } + startTime = node->getEarlyStart(); + endTime = std::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; - } +// 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 successors is itself?"); + if (bb1 == bb) + succ_bb = bb2; + else + succ_bb = bb1; + return succ_bb; + } } - assert( 0 && "NO Successor?"); + 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; - } +// 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)); - +// 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){ + 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]; - } + 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 consitent with core table"); + // move the schedule one iteration ahead and overlap with the original + tempSchedule_prologue[round * II + i][j] = schedule[i][j]; + } + } } } - //clear the clone memory in the core schedule instructions + // 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()); - } + + // 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){ +// 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); + 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]) { + + // Take care of branch instruction differently with normal instructions + if (BranchInst::classof(coreSchedule[i][j]->getInst())) { + brchInst = (BranchInst *) coreSchedule[i][j]->getInst(); + continue; + } + // 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); + // 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); + // 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()); + // 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); + // 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(); + Instruction *cond = (Instruction *) cln->getCondition(); //get the condition's second operand, it should be a constant - Value* operand=cond->getOperand(1); + 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); + 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) +{ - - -//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 ){ + 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]; - } + 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); - } + 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() ); + 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); + 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 |