diff options
Diffstat (limited to 'lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp')
| -rw-r--r-- | lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp | 984 |
1 files changed, 18 insertions, 966 deletions
diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp index 49f4246c02..bad3e97e48 100644 --- a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp @@ -1,983 +1,35 @@ -//===- ModuloScheduling.cpp - Modulo Software Pipelining ------------------===// +//===-- ModuloScheduling.cpp - Software Pipeling Approach - SMS --*- C++ -*--=// // -// Implements the llvm/CodeGen/ModuloScheduling.h interface +// The is a software pipelining pass based on the Swing Modulo Scheduling +// alogrithm (SMS). // //===----------------------------------------------------------------------===// -#include "llvm/BasicBlock.h" -#include "llvm/Constants.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 "Support/Statistic.h" #include "ModuloSchedGraph.h" -#include "ModuloScheduling.h" -#include <algorithm> -#include <fstream> -//************************************************************ -// 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() -//************************************************************ +#include "llvm/Pass.h" +#include "llvm/Function.h" -ModuloSchedDebugLevel_t ModuloSchedDebugLevel; - -cl::opt<ModuloSchedDebugLevel_t,true> -SDL_opt("modsched", cl::Hidden, cl::location(ModuloSchedDebugLevel), - cl::desc("enable modulo scheduling debugging information"), - cl::values(clEnumValN(ModuloSchedDebugLevel_NoDebugInfo, - "none", "disable debug output"), - clEnumValN(ModuloSchedDebugLevel_PrintSchedule, - "psched", "print original and new schedule"), - clEnumValN(ModuloSchedDebugLevel_PrintScheduleProcess, - "pschedproc", - "print how the new schdule is produced"), - 0)); - -// Computes the schedule and inserts epilogue and prologue -// -void -ModuloScheduling::instrScheduling(){ - - - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "************ computing modulo schedule ***********\n"); - - const TargetSchedInfo & 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 (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "increase II to " << II << "\n"); - } - } - - //print the final schedule - dumpFinalSchedule(); - - //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 (ModuloScheduling::printSchedule()) { - DEBUG_PRINT(std::cerr << "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);*/ +namespace { - //print the BasicBlocks if necessary -// if (0){ -// DEBUG_PRINT(std::cerr << "dumping the prologue block:\n"); -// graph.dump(prologue); -// DEBUG_PRINT(std::cerr << "dumping the kernel block\n"); -// graph.dump(kernel); -// DEBUG_PRINT(std::cerr << "dumping the epilogue block\n"); -// graph.dump(epilogue); -// } - -} - - -// 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 (ModuloScheduling::printScheduleProcess()) { - DEBUG_PRINT(std::cerr << "***** new round with II= " << II << " ***********\n"); - DEBUG_PRINT(std::cerr << - " ************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 (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "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 (ModuloScheduling::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)); - } - 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)); - } - 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)); - } - 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 (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "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 successors 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 std::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 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 - 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]) { - - // 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); - 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 - cln->setSuccessor(0, kernel); - // set the second successor to eiplogue - 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 std::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 TargetSchedInfo & msi = target.getSchedInfo(); - unsigned int numIssueSlots = msi.maxNumIssueTotal; - - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "startTime= " << start << " endTime= " << end << "\n"); - bool isScheduled = false; - for (unsigned i = start; i <= end; i++) { - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << " now try cycle " << i << ":" << "\n"); - for (unsigned j = 0; j < numIssueSlots; j++) { - unsigned int core_i = i % II; - unsigned int core_j = j; - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "\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 TargetInstrInfo & 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 += std::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 += std::max(mii.minLatency(minstr->getOpCode()), 1); - } - resourceConflict = true; - } - } - if (!resourceConflict && !coreSchedule[core_i][core_j]) { - if (ModuloScheduling::printScheduleProcess()) { - DEBUG_PRINT(std::cerr << " OK!" << "\n"); - DEBUG_PRINT(std::cerr << "Node " << node->getNodeId() << " scheduled.\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); - } - std::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 (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << " Slot not available\n"); - } else { - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << " Resource conflicts\n"); - } - } - if (isScheduled) - break; - } - //assert(nodeScheduled &&"this node can not be scheduled?"); - return isScheduled; -} - - -void -ModuloScheduling::updateResourceTable(Resources useResources, - int startCycle){ - - for (unsigned i = 0; i < useResources.size(); i++) { - int absCycle = startCycle + i; - int coreCycle = absCycle % II; - std::vector<std::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(Resources useResources, - int startCycle){ - - for (unsigned i = 0; i < useResources.size(); i++) { - int absCycle = startCycle + i; - int coreCycle = absCycle % II; - std::vector<std::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: resourceTableNegative -// 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(){ - - DEBUG_PRINT(std::cerr << "dumping resource usage table\n"); - for (unsigned i = 0; i < resourceTable.size(); i++) { - for (unsigned j = 0; j < resourceTable[i].size(); j++) - DEBUG_PRINT(std::cerr << resourceTable[i][j].first - << ":" << resourceTable[i][j].second << " "); - DEBUG_PRINT(std::cerr << "\n"); - } - -} - -//---------------------------------------------------------------------- -//Function: dumpSchedule -//Purpose: -// print out thisSchedule for debug -// -//----------------------------------------------------------------------- -void -ModuloScheduling::dumpSchedule(vvNodeType thisSchedule){ - - const TargetSchedInfo & msi = target.getSchedInfo(); - unsigned numIssueSlots = msi.maxNumIssueTotal; - for (unsigned i = 0; i < numIssueSlots; i++) - DEBUG_PRINT(std::cerr << "\t#"); - DEBUG_PRINT(std::cerr << "\n"); - for (unsigned i = 0; i < thisSchedule.size(); i++) { - DEBUG_PRINT(std::cerr << "cycle" << i << ": "); - for (unsigned j = 0; j < thisSchedule[i].size(); j++) - if (thisSchedule[i][j] != NULL) - DEBUG_PRINT(std::cerr << thisSchedule[i][j]->getNodeId() << "\t"); - else - DEBUG_PRINT(std::cerr << "\t"); - DEBUG_PRINT(std::cerr << "\n"); - } -} - - -//---------------------------------------------------- -//Function: dumpScheduling -//Purpose: -// print out the schedule and coreSchedule for debug -// -//------------------------------------------------------- - -void -ModuloScheduling::dumpScheduling(){ - - DEBUG_PRINT(std::cerr << "dump schedule:" << "\n"); - const TargetSchedInfo & msi = target.getSchedInfo(); - unsigned numIssueSlots = msi.maxNumIssueTotal; - for (unsigned i = 0; i < numIssueSlots; i++) - DEBUG_PRINT(std::cerr << "\t#"); - DEBUG_PRINT(std::cerr << "\n"); - for (unsigned i = 0; i < schedule.size(); i++) { - DEBUG_PRINT(std::cerr << "cycle" << i << ": "); - for (unsigned j = 0; j < schedule[i].size(); j++) - if (schedule[i][j] != NULL) - DEBUG_PRINT(std::cerr << schedule[i][j]->getNodeId() << "\t"); - else - DEBUG_PRINT(std::cerr << "\t"); - DEBUG_PRINT(std::cerr << "\n"); - } - - DEBUG_PRINT(std::cerr << "dump coreSchedule:" << "\n"); - for (unsigned i = 0; i < numIssueSlots; i++) - DEBUG_PRINT(std::cerr << "\t#"); - DEBUG_PRINT(std::cerr << "\n"); - for (unsigned i = 0; i < coreSchedule.size(); i++) { - DEBUG_PRINT(std::cerr << "cycle" << i << ": "); - for (unsigned j = 0; j < coreSchedule[i].size(); j++) - if (coreSchedule[i][j] != NULL) - DEBUG_PRINT(std::cerr << coreSchedule[i][j]->getNodeId() << "\t"); - else - DEBUG_PRINT(std::cerr << "\t"); - DEBUG_PRINT(std::cerr << "\n"); - } -} - -/* - print out final schedule -*/ - -void -ModuloScheduling::dumpFinalSchedule(){ - - std::cerr << "dump schedule:" << "\n"; - const TargetSchedInfo & msi = target.getSchedInfo(); - unsigned numIssueSlots = msi.maxNumIssueTotal; - - for (unsigned i = 0; i < numIssueSlots; i++) - std::cerr << "\t#"; - std::cerr << "\n"; - - for (unsigned i = 0; i < schedule.size(); i++) { - std::cerr << "cycle" << i << ": "; + class ModuloScheduling : public FunctionPass { - for (unsigned j = 0; j < schedule[i].size(); j++) - if (schedule[i][j] != NULL) - std::cerr << schedule[i][j]->getNodeId() << "\t"; - else - std::cerr << "\t"; - std::cerr << "\n"; - } - - std::cerr << "dump coreSchedule:" << "\n"; - for (unsigned i = 0; i < numIssueSlots; i++) - std::cerr << "\t#"; - std::cerr << "\n"; - - for (unsigned i = 0; i < coreSchedule.size(); i++) { - std::cerr << "cycle" << i << ": "; - for (unsigned j = 0; j < coreSchedule[i].size(); j++) - if (coreSchedule[i][j] != NULL) - std::cerr << coreSchedule[i][j]->getNodeId() << "\t"; - else - std::cerr << "\t"; - std::cerr << "\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); + virtual bool runOnFunction(Function &F); }; -} // end anonymous namespace + RegisterOpt<ModuloScheduling> X("modulo-sched", "Modulo Scheduling/Software Pipelining"); +} -bool -ModuloSchedulingPass::runOnFunction(Function &F){ - - ModuloSchedGraphSet *graphSet = new ModuloSchedGraphSet(&F, target); - - ModuloSchedulingSet ModuloSchedulingSet(*graphSet); - - DEBUG_PRINT(std::cerr<<"runOnFunction in ModuloSchedulingPass returns\n"<<"\n"); - return false; +//Create Modulo Scheduling Pass +Pass *createModuloSchedPass() { + return new ModuloScheduling(); } +//ModuloScheduling::runOnFunction - Main transformation entry point. +bool ModuloScheduling::runOnFunction(Function &F) { + bool Changed = false; -Pass * -createModuloSchedulingPass(const TargetMachine & tgt){ - DEBUG_PRINT(std::cerr<<"creating modulo scheduling\n"); - return new ModuloSchedulingPass(tgt); + return Changed; } + |