1 //===- ModuloScheduling.cpp - Modulo Software Pipelining ------------------===//
3 // Implements the llvm/CodeGen/ModuloScheduling.h interface
5 //===----------------------------------------------------------------------===//
7 //#include "llvm/CodeGen/MachineCodeForBasicBlock.h"
8 //#include "llvm/CodeGen/MachineCodeForMethod.h"
9 //#include "llvm/Analysis/LiveVar/FunctionLiveVarInfo.h" // FIXME: Remove when modularized better
10 #include "llvm/BasicBlock.h"
11 #include "llvm/Constants.h"
12 #include "llvm/Instruction.h"
13 #include "llvm/iTerminators.h"
14 #include "llvm/iPHINode.h"
15 #include "llvm/CodeGen/MachineInstr.h"
16 #include "llvm/CodeGen/MachineCodeForInstruction.h"
17 #include "llvm/CodeGen/MachineFunction.h"
18 #include "llvm/CodeGen/InstrSelection.h"
19 #include "llvm/Target/TargetSchedInfo.h"
20 #include "llvm/Target/TargetMachine.h"
21 #include "Support/CommandLine.h"
22 #include "Support/Statistic.h"
23 #include "ModuloSchedGraph.h"
24 #include "ModuloScheduling.h"
30 //************************************************************
31 // printing Debug information
32 // ModuloSchedDebugLevel stores the value of debug level
33 // modsched_os is the ostream to dump debug information, which is written into
34 // the file 'moduloSchedDebugInfo.output'
35 // see ModuloSchedulingPass::runOnFunction()
36 //************************************************************
38 ModuloSchedDebugLevel_t ModuloSchedDebugLevel;
40 cl::opt<ModuloSchedDebugLevel_t,true>
41 SDL_opt("modsched", cl::Hidden, cl::location(ModuloSchedDebugLevel),
42 cl::desc("enable modulo scheduling debugging information"),
43 cl::values(clEnumValN(ModuloSchedDebugLevel_NoDebugInfo,
44 "none", "disable debug output"),
45 clEnumValN(ModuloSchedDebugLevel_PrintSchedule,
46 "psched", "print original and new schedule"),
47 clEnumValN(ModuloSchedDebugLevel_PrintScheduleProcess,
49 "print how the new schdule is produced"),
52 // Computes the schedule and inserts epilogue and prologue
54 void ModuloScheduling::instrScheduling()
56 if (ModuloScheduling::printScheduleProcess())
57 DEBUG(std::cerr << "************ computing modulo schedule ***********\n");
59 const TargetSchedInfo & msi = target.getSchedInfo();
61 //number of issue slots in the in each cycle
62 int numIssueSlots = msi.maxNumIssueTotal;
64 //compute the schedule
67 //clear memory from the last round and initialize if necessary
70 //compute schedule and coreSchedule with the current II
71 success = computeSchedule();
75 if (ModuloScheduling::printScheduleProcess())
76 DEBUG(std::cerr << "increase II to " << II << "\n");
80 //print the final schedule if necessary
81 if (ModuloScheduling::printSchedule())
84 //the schedule has been computed
85 //create epilogue, prologue and kernel BasicBlock
87 //find the successor for this BasicBlock
88 BasicBlock *succ_bb = getSuccBB(bb);
90 //print the original BasicBlock if necessary
91 if (ModuloScheduling::printSchedule()) {
92 DEBUG(std::cerr << "dumping the orginal block\n");
95 //construction of prologue, kernel and epilogue
96 BasicBlock *kernel = bb->splitBasicBlock(bb->begin());
97 BasicBlock *prologue = bb;
98 BasicBlock *epilogue = kernel->splitBasicBlock(kernel->begin());
100 // Construct prologue
101 constructPrologue(prologue);
104 constructKernel(prologue, kernel, epilogue);
106 // Construct epilogue
107 constructEpilogue(epilogue, succ_bb);
109 //print the BasicBlocks if necessary
110 if (ModuloScheduling::printSchedule()) {
111 DEBUG(std::cerr << "dumping the prologue block:\n");
112 graph.dump(prologue);
113 DEBUG(std::cerr << "dumping the kernel block\n");
115 DEBUG(std::cerr << "dumping the epilogue block\n");
116 graph.dump(epilogue);
120 // Clear memory from the last round and initialize if necessary
122 void ModuloScheduling::clearInitMem(const TargetSchedInfo & msi)
124 unsigned numIssueSlots = msi.maxNumIssueTotal;
125 // clear nodeScheduled from the last round
126 if (ModuloScheduling::printScheduleProcess()) {
127 DEBUG(std::cerr << "***** new round with II= " << II << " ***********\n");
129 " ************clear the vector nodeScheduled*************\n");
131 nodeScheduled.clear();
133 // clear resourceTable from the last round and reset it
134 resourceTable.clear();
135 for (unsigned i = 0; i < II; ++i)
136 resourceTable.push_back(msi.resourceNumVector);
138 // clear the schdule and coreSchedule from the last round
140 coreSchedule.clear();
142 // create a coreSchedule of size II*numIssueSlots
143 // each entry is NULL
144 while (coreSchedule.size() < II) {
145 std::vector < ModuloSchedGraphNode * >*newCycle =
146 new std::vector < ModuloSchedGraphNode * >();
147 for (unsigned k = 0; k < numIssueSlots; ++k)
148 newCycle->push_back(NULL);
149 coreSchedule.push_back(*newCycle);
153 // Compute schedule and coreSchedule with the current II
155 bool ModuloScheduling::computeSchedule()
158 if (ModuloScheduling::printScheduleProcess())
159 DEBUG(std::cerr << "start to compute schedule\n");
161 // Loop over the ordered nodes
162 for (NodeVec::const_iterator I = oNodes.begin(); I != oNodes.end(); ++I) {
163 // Try to schedule for node I
164 if (ModuloScheduling::printScheduleProcess())
166 ModuloSchedGraphNode *node = *I;
168 // Compute whether this node has successor(s)
171 // Compute whether this node has predessor(s)
174 NodeVec schSucc = graph.vectorConj(nodeScheduled, graph.succSet(node));
177 NodeVec schPred = graph.vectorConj(nodeScheduled, graph.predSet(node));
181 //startTime: the earliest time we will try to schedule this node
182 //endTime: the latest time we will try to schedule this node
183 int startTime, endTime;
185 //node's earlyStart: possible earliest time to schedule this node
186 //node's lateStart: possible latest time to schedule this node
187 node->setEarlyStart(-1);
188 node->setLateStart(9999);
190 //this node has predessor but no successor
192 // This node's earlyStart is it's predessor's schedule time + the edge
193 // delay - the iteration difference* II
194 for (unsigned i = 0; i < schPred.size(); i++) {
195 ModuloSchedGraphNode *predNode = schPred[i];
196 SchedGraphEdge *edge =
197 graph.getMaxDelayEdge(predNode->getNodeId(),
200 predNode->getSchTime() + edge->getMinDelay() -
201 edge->getIteDiff() * II;
202 node->setEarlyStart(std::max(node->getEarlyStart(), temp));
204 startTime = node->getEarlyStart();
205 endTime = node->getEarlyStart() + II - 1;
207 // This node has a successor but no predecessor
209 for (unsigned i = 0; i < schSucc.size(); ++i) {
210 ModuloSchedGraphNode *succNode = schSucc[i];
211 SchedGraphEdge *edge =
212 graph.getMaxDelayEdge(succNode->getNodeId(),
215 succNode->getSchTime() - edge->getMinDelay() +
216 edge->getIteDiff() * II;
217 node->setLateStart(std::min(node->getEarlyStart(), temp));
219 startTime = node->getLateStart() - II + 1;
220 endTime = node->getLateStart();
222 // This node has both successors and predecessors
224 for (unsigned i = 0; i < schPred.size(); ++i) {
225 ModuloSchedGraphNode *predNode = schPred[i];
226 SchedGraphEdge *edge =
227 graph.getMaxDelayEdge(predNode->getNodeId(),
230 predNode->getSchTime() + edge->getMinDelay() -
231 edge->getIteDiff() * II;
232 node->setEarlyStart(std::max(node->getEarlyStart(), temp));
234 for (unsigned i = 0; i < schSucc.size(); ++i) {
235 ModuloSchedGraphNode *succNode = schSucc[i];
236 SchedGraphEdge *edge =
237 graph.getMaxDelayEdge(succNode->getNodeId(),
240 succNode->getSchTime() - edge->getMinDelay() +
241 edge->getIteDiff() * II;
242 node->setLateStart(std::min(node->getEarlyStart(), temp));
244 startTime = node->getEarlyStart();
245 endTime = std::min(node->getLateStart(),
246 node->getEarlyStart() + ((int) II) - 1);
248 //this node has no successor or predessor
249 if (!succ && !pred) {
250 node->setEarlyStart(node->getASAP());
251 startTime = node->getEarlyStart();
252 endTime = node->getEarlyStart() + II - 1;
254 //try to schedule this node based on the startTime and endTime
255 if (ModuloScheduling::printScheduleProcess())
256 DEBUG(std::cerr << "scheduling the node " << (*I)->getNodeId() << "\n");
259 this->ScheduleNode(node, startTime, endTime, nodeScheduled);
267 // Get the successor of the BasicBlock
269 BasicBlock *ModuloScheduling::getSuccBB(BasicBlock *bb)
272 for (unsigned i = 0; i < II; ++i)
273 for (unsigned j = 0; j < coreSchedule[i].size(); ++j)
274 if (coreSchedule[i][j]) {
275 const Instruction *ist = coreSchedule[i][j]->getInst();
277 //we can get successor from the BranchInst instruction
278 //assume we only have one successor (besides itself) here
279 if (BranchInst::classof(ist)) {
280 BranchInst *bi = (BranchInst *) ist;
281 assert(bi->isConditional() &&
282 "the branchInst is not a conditional one");
283 assert(bi->getNumSuccessors() == 2
284 && " more than two successors?");
285 BasicBlock *bb1 = bi->getSuccessor(0);
286 BasicBlock *bb2 = bi->getSuccessor(1);
287 assert((bb1 == bb || bb2 == bb) &&
288 " None of its successors is itself?");
296 assert(0 && "NO Successor?");
301 // Get the predecessor of the BasicBlock
303 BasicBlock *ModuloScheduling::getPredBB(BasicBlock *bb)
306 for (unsigned i = 0; i < II; ++i)
307 for (unsigned j = 0; j < coreSchedule[i].size(); ++j)
308 if (coreSchedule[i][j]) {
309 const Instruction *ist = coreSchedule[i][j]->getInst();
311 //we can get predecessor from the PHINode instruction
312 //assume we only have one predecessor (besides itself) here
313 if (PHINode::classof(ist)) {
314 PHINode *phi = (PHINode *) ist;
315 assert(phi->getNumIncomingValues() == 2 &&
316 " the number of incoming value is not equal to two? ");
317 BasicBlock *bb1 = phi->getIncomingBlock(0);
318 BasicBlock *bb2 = phi->getIncomingBlock(1);
319 assert((bb1 == bb || bb2 == bb) &&
320 " None of its predecessor is itself?");
328 assert(0 && " no predecessor?");
333 // Construct the prologue
335 void ModuloScheduling::constructPrologue(BasicBlock *prologue)
337 InstListType & prologue_ist = prologue->getInstList();
338 vvNodeType & tempSchedule_prologue =
339 *(new std::vector<std::vector<ModuloSchedGraphNode*> >(schedule));
341 //compute the schedule for prologue
343 unsigned scheduleSize = schedule.size();
344 while (round < scheduleSize / II) {
346 for (unsigned i = 0; i < scheduleSize; ++i) {
347 if (round * II + i >= scheduleSize)
349 for (unsigned j = 0; j < schedule[i].size(); ++j) {
350 if (schedule[i][j]) {
351 assert(tempSchedule_prologue[round * II + i][j] == NULL &&
352 "table not consitent with core table");
353 // move the schedule one iteration ahead and overlap with the original
354 tempSchedule_prologue[round * II + i][j] = schedule[i][j];
360 // Clear the clone memory in the core schedule instructions
363 // Fill in the prologue
364 for (unsigned i = 0; i < ceil(1.0 * scheduleSize / II - 1) * II; ++i)
365 for (unsigned j = 0; j < tempSchedule_prologue[i].size(); ++j)
366 if (tempSchedule_prologue[i][j]) {
368 //get the instruction
370 (Instruction *) tempSchedule_prologue[i][j]->getInst();
373 Instruction *cln = cloneInstSetMemory(orn);
375 //insert the instruction
376 prologue_ist.insert(prologue_ist.back(), cln);
378 //if there is PHINode in the prologue, the incoming value from itself
379 //should be removed because it is not a loop any longer
380 if (PHINode::classof(cln)) {
381 PHINode *phi = (PHINode *) cln;
382 phi->removeIncomingValue(phi->getParent());
388 // Construct the kernel BasicBlock
390 void ModuloScheduling::constructKernel(BasicBlock *prologue,
392 BasicBlock *epilogue)
394 //*************fill instructions in the kernel****************
395 InstListType & kernel_ist = kernel->getInstList();
396 BranchInst *brchInst;
397 PHINode *phiInst, *phiCln;
399 for (unsigned i = 0; i < coreSchedule.size(); ++i)
400 for (unsigned j = 0; j < coreSchedule[i].size(); ++j)
401 if (coreSchedule[i][j]) {
403 // Take care of branch instruction differently with normal instructions
404 if (BranchInst::classof(coreSchedule[i][j]->getInst())) {
405 brchInst = (BranchInst *) coreSchedule[i][j]->getInst();
408 // Take care of PHINode instruction differently with normal instructions
409 if (PHINode::classof(coreSchedule[i][j]->getInst())) {
410 phiInst = (PHINode *) coreSchedule[i][j]->getInst();
411 Instruction *cln = cloneInstSetMemory(phiInst);
412 kernel_ist.insert(kernel_ist.back(), cln);
413 phiCln = (PHINode *) cln;
416 //for normal instructions: made a clone and insert it in the kernel_ist
418 cloneInstSetMemory((Instruction *) coreSchedule[i][j]->
420 kernel_ist.insert(kernel_ist.back(), cln);
422 // The two incoming BasicBlock for PHINode is the prologue and the kernel
424 phiCln->setIncomingBlock(0, prologue);
425 phiCln->setIncomingBlock(1, kernel);
427 // The incoming value for the kernel (itself) is the new value which is
428 // computed in the kernel
429 Instruction *originalVal = (Instruction *) phiInst->getIncomingValue(1);
430 phiCln->setIncomingValue(1, originalVal->getClone());
432 // Make a clone of the branch instruction and insert it in the end
433 BranchInst *cln = (BranchInst *) cloneInstSetMemory(brchInst);
434 kernel_ist.insert(kernel_ist.back(), cln);
436 // delete the unconditional branch instruction, which is generated when
437 // splitting the basicBlock
438 kernel_ist.erase(--kernel_ist.end());
440 // set the first successor to itself
441 ((BranchInst *) cln)->setSuccessor(0, kernel);
442 // set the second successor to eiplogue
443 ((BranchInst *) cln)->setSuccessor(1, epilogue);
445 //*****change the condition*******
447 //get the condition instruction
448 Instruction *cond = (Instruction *) cln->getCondition();
450 //get the condition's second operand, it should be a constant
451 Value *operand = cond->getOperand(1);
452 assert(ConstantSInt::classof(operand));
454 //change the constant in the condtion instruction
455 ConstantSInt *iteTimes =
456 ConstantSInt::get(operand->getType(),
457 ((ConstantSInt *) operand)->getValue() - II + 1);
458 cond->setOperand(1, iteTimes);
463 // Construct the epilogue
465 void ModuloScheduling::constructEpilogue(BasicBlock *epilogue,
469 //compute the schedule for epilogue
470 vvNodeType &tempSchedule_epilogue =
471 *(new std::vector<std::vector<ModuloSchedGraphNode*> >(schedule));
472 unsigned scheduleSize = schedule.size();
474 while (round < ceil(1.0 * scheduleSize / II) - 1) {
476 for (unsigned i = 0; i < scheduleSize; i++) {
477 if (i + round * II >= scheduleSize)
479 for (unsigned j = 0; j < schedule[i].size(); j++)
480 if (schedule[i + round * II][j]) {
481 assert(tempSchedule_epilogue[i][j] == NULL
482 && "table not consitant with core table");
484 //move the schdule one iteration behind and overlap
485 tempSchedule_epilogue[i][j] = schedule[i + round * II][j];
490 //fill in the epilogue
491 InstListType & epilogue_ist = epilogue->getInstList();
492 for (unsigned i = II; i < scheduleSize; i++)
493 for (unsigned j = 0; j < tempSchedule_epilogue[i].size(); j++)
494 if (tempSchedule_epilogue[i][j]) {
496 (Instruction *) tempSchedule_epilogue[i][j]->getInst();
498 //BranchInst and PHINode should be treated differently
499 //BranchInst:unecessary, simly omitted
501 if (!BranchInst::classof(inst) && !PHINode::classof(inst)) {
502 //make a clone instruction and insert it into the epilogue
503 Instruction *cln = cloneInstSetMemory(inst);
504 epilogue_ist.push_front(cln);
508 //*************delete the original instructions****************//
509 //to delete the original instructions, we have to make sure their use is zero
511 //update original core instruction's uses, using its clone instread
512 for (unsigned i = 0; i < II; i++)
513 for (unsigned j = 0; j < coreSchedule[i].size(); j++) {
514 if (coreSchedule[i][j])
515 updateUseWithClone((Instruction *) coreSchedule[i][j]->getInst());
518 //erase these instructions
519 for (unsigned i = 0; i < II; i++)
520 for (unsigned j = 0; j < coreSchedule[i].size(); j++)
521 if (coreSchedule[i][j]) {
522 Instruction *ist = (Instruction *) coreSchedule[i][j]->getInst();
523 ist->getParent()->getInstList().erase(ist);
525 //**************************************************************//
528 //finally, insert an unconditional branch instruction at the end
529 epilogue_ist.push_back(new BranchInst(succ_bb));
534 //------------------------------------------------------------------------------
535 //this function replace the value(instruction) ist in other instructions with
536 //its latest clone i.e. after this function is called, the ist is not used
537 //anywhere and it can be erased.
538 //------------------------------------------------------------------------------
539 void ModuloScheduling::updateUseWithClone(Instruction * ist)
542 while (ist->use_size() > 0) {
543 bool destroyed = false;
545 //other instruction is using this value ist
546 assert(Instruction::classof(*ist->use_begin()));
547 Instruction *inst = (Instruction *) (*ist->use_begin());
549 for (unsigned i = 0; i < inst->getNumOperands(); i++)
550 if (inst->getOperand(i) == ist && ist->getClone()) {
551 // if the instruction is TmpInstruction, simly delete it because it has
552 // no parent and it does not belongs to any BasicBlock
553 if (TmpInstruction::classof(inst)) {
559 //otherwise, set the instruction's operand to the value's clone
560 inst->setOperand(i, ist->getClone());
562 //the use from the original value ist is destroyed
567 //if the use can not be destroyed , something is wrong
569 assert(0 && "this use can not be destroyed");
576 //********************************************************
577 //this function clear all clone mememoy
578 //i.e. set all instruction's clone memory to NULL
579 //*****************************************************
580 void ModuloScheduling::clearCloneMemory()
582 for (unsigned i = 0; i < coreSchedule.size(); i++)
583 for (unsigned j = 0; j < coreSchedule[i].size(); j++)
584 if (coreSchedule[i][j])
585 ((Instruction *) coreSchedule[i][j]->getInst())->clearClone();
590 //******************************************************************************
591 // this function make a clone of the instruction orn the cloned instruction will
592 // use the orn's operands' latest clone as its operands it is done this way
593 // because LLVM is in SSA form and we should use the correct value
594 //this fuction also update the instruction orn's latest clone memory
595 //******************************************************************************
596 Instruction *ModuloScheduling::cloneInstSetMemory(Instruction * orn)
598 // make a clone instruction
599 Instruction *cln = orn->clone();
601 // update the operands
602 for (unsigned k = 0; k < orn->getNumOperands(); k++) {
603 const Value *op = orn->getOperand(k);
604 if (Instruction::classof(op) && ((Instruction *) op)->getClone()) {
605 Instruction *op_inst = (Instruction *) op;
606 cln->setOperand(k, op_inst->getClone());
610 // update clone memory
617 bool ModuloScheduling::ScheduleNode(ModuloSchedGraphNode * node,
618 unsigned start, unsigned end,
619 NodeVec & nodeScheduled)
621 const TargetSchedInfo & msi = target.getSchedInfo();
622 unsigned int numIssueSlots = msi.maxNumIssueTotal;
624 if (ModuloScheduling::printScheduleProcess())
625 DEBUG(std::cerr << "startTime= " << start << " endTime= " << end << "\n");
626 bool isScheduled = false;
627 for (unsigned i = start; i <= end; i++) {
628 if (ModuloScheduling::printScheduleProcess())
629 DEBUG(std::cerr << " now try cycle " << i << ":" << "\n");
630 for (unsigned j = 0; j < numIssueSlots; j++) {
631 unsigned int core_i = i % II;
632 unsigned int core_j = j;
633 if (ModuloScheduling::printScheduleProcess())
634 DEBUG(std::cerr << "\t Trying slot " << j << "...........");
635 //check the resouce table, make sure there is no resource conflicts
636 const Instruction *instr = node->getInst();
637 MachineCodeForInstruction & tempMvec =
638 MachineCodeForInstruction::get(instr);
639 bool resourceConflict = false;
640 const TargetInstrInfo & mii = msi.getInstrInfo();
642 if (coreSchedule.size() < core_i + 1
643 || !coreSchedule[core_i][core_j]) {
644 //this->dumpResourceUsageTable();
646 for (unsigned k = 0; k < tempMvec.size(); k++) {
647 MachineInstr *minstr = tempMvec[k];
648 InstrRUsage rUsage = msi.getInstrRUsage(minstr->getOpCode());
649 std::vector < std::vector < resourceId_t > >resources
650 = rUsage.resourcesByCycle;
651 updateResourceTable(resources, i + latency);
652 latency += std::max(mii.minLatency(minstr->getOpCode()), 1);
655 //this->dumpResourceUsageTable();
658 if (resourceTableNegative()) {
660 //undo-update the resource table
661 for (unsigned k = 0; k < tempMvec.size(); k++) {
662 MachineInstr *minstr = tempMvec[k];
663 InstrRUsage rUsage = msi.getInstrRUsage(minstr->getOpCode());
664 std::vector < std::vector < resourceId_t > >resources
665 = rUsage.resourcesByCycle;
666 undoUpdateResourceTable(resources, i + latency);
667 latency += std::max(mii.minLatency(minstr->getOpCode()), 1);
669 resourceConflict = true;
672 if (!resourceConflict && !coreSchedule[core_i][core_j]) {
673 if (ModuloScheduling::printScheduleProcess()) {
674 DEBUG(std::cerr << " OK!" << "\n");
675 DEBUG(std::cerr << "Node " << node->getNodeId() << " scheduled.\n");
677 //schedule[i][j]=node;
678 while (schedule.size() <= i) {
679 std::vector < ModuloSchedGraphNode * >*newCycle =
680 new std::vector < ModuloSchedGraphNode * >();
681 for (unsigned k = 0; k < numIssueSlots; k++)
682 newCycle->push_back(NULL);
683 schedule.push_back(*newCycle);
685 std::vector<ModuloSchedGraphNode*>::iterator startIterator;
686 startIterator = schedule[i].begin();
687 schedule[i].insert(startIterator + j, node);
688 startIterator = schedule[i].begin();
689 schedule[i].erase(startIterator + j + 1);
691 //update coreSchedule
692 //coreSchedule[core_i][core_j]=node;
693 while (coreSchedule.size() <= core_i) {
694 std::vector<ModuloSchedGraphNode*> *newCycle =
695 new std::vector<ModuloSchedGraphNode*>();
696 for (unsigned k = 0; k < numIssueSlots; k++)
697 newCycle->push_back(NULL);
698 coreSchedule.push_back(*newCycle);
701 startIterator = coreSchedule[core_i].begin();
702 coreSchedule[core_i].insert(startIterator + core_j, node);
703 startIterator = coreSchedule[core_i].begin();
704 coreSchedule[core_i].erase(startIterator + core_j + 1);
708 nodeScheduled.push_back(node);
711 } else if (coreSchedule[core_i][core_j]) {
712 if (ModuloScheduling::printScheduleProcess())
713 DEBUG(std::cerr << " Slot not available\n");
715 if (ModuloScheduling::printScheduleProcess())
716 DEBUG(std::cerr << " Resource conflicts\n");
722 //assert(nodeScheduled &&"this node can not be scheduled?");
727 void ModuloScheduling::updateResourceTable(Resources useResources,
730 for (unsigned i = 0; i < useResources.size(); i++) {
731 int absCycle = startCycle + i;
732 int coreCycle = absCycle % II;
733 std::vector<std::pair<int,int> > &resourceRemained =
734 resourceTable[coreCycle];
735 std::vector < unsigned int >&resourceUsed = useResources[i];
736 for (unsigned j = 0; j < resourceUsed.size(); j++) {
737 for (unsigned k = 0; k < resourceRemained.size(); k++)
738 if ((int) resourceUsed[j] == resourceRemained[k].first) {
739 resourceRemained[k].second--;
745 void ModuloScheduling::undoUpdateResourceTable(Resources useResources,
748 for (unsigned i = 0; i < useResources.size(); i++) {
749 int absCycle = startCycle + i;
750 int coreCycle = absCycle % II;
751 std::vector<std::pair<int,int> > &resourceRemained =
752 resourceTable[coreCycle];
753 std::vector < unsigned int >&resourceUsed = useResources[i];
754 for (unsigned j = 0; j < resourceUsed.size(); j++) {
755 for (unsigned k = 0; k < resourceRemained.size(); k++)
756 if ((int) resourceUsed[j] == resourceRemained[k].first) {
757 resourceRemained[k].second++;
764 //-----------------------------------------------------------------------
765 // Function: resourceTableNegative
767 // return false if any element in the resouceTable is negative
768 // otherwise return true
771 // this function is used to determine if an instruction is eligible for
772 // schedule at certain cycle
773 //-----------------------------------------------------------------------
776 bool ModuloScheduling::resourceTableNegative()
778 assert(resourceTable.size() == (unsigned) II
779 && "resouceTable size must be equal to II");
780 bool isNegative = false;
781 for (unsigned i = 0; i < resourceTable.size(); i++)
782 for (unsigned j = 0; j < resourceTable[i].size(); j++) {
783 if (resourceTable[i][j].second < 0) {
792 //----------------------------------------------------------------------
793 // Function: dumpResouceUsageTable
795 // print out ResouceTable for debug
797 //------------------------------------------------------------------------
799 void ModuloScheduling::dumpResourceUsageTable()
801 DEBUG(std::cerr << "dumping resource usage table\n");
802 for (unsigned i = 0; i < resourceTable.size(); i++) {
803 for (unsigned j = 0; j < resourceTable[i].size(); j++)
804 DEBUG(std::cerr << resourceTable[i][j].first
805 << ":" << resourceTable[i][j].second << " ");
806 DEBUG(std::cerr << "\n");
811 //----------------------------------------------------------------------
812 //Function: dumpSchedule
814 // print out thisSchedule for debug
816 //-----------------------------------------------------------------------
817 void ModuloScheduling::dumpSchedule(vvNodeType thisSchedule)
819 const TargetSchedInfo & msi = target.getSchedInfo();
820 unsigned numIssueSlots = msi.maxNumIssueTotal;
821 for (unsigned i = 0; i < numIssueSlots; i++)
822 DEBUG(std::cerr << "\t#");
823 DEBUG(std::cerr << "\n");
824 for (unsigned i = 0; i < thisSchedule.size(); i++) {
825 DEBUG(std::cerr << "cycle" << i << ": ");
826 for (unsigned j = 0; j < thisSchedule[i].size(); j++)
827 if (thisSchedule[i][j] != NULL)
828 DEBUG(std::cerr << thisSchedule[i][j]->getNodeId() << "\t");
830 DEBUG(std::cerr << "\t");
831 DEBUG(std::cerr << "\n");
836 //----------------------------------------------------
837 //Function: dumpScheduling
839 // print out the schedule and coreSchedule for debug
841 //-------------------------------------------------------
843 void ModuloScheduling::dumpScheduling()
845 DEBUG(std::cerr << "dump schedule:" << "\n");
846 const TargetSchedInfo & msi = target.getSchedInfo();
847 unsigned numIssueSlots = msi.maxNumIssueTotal;
848 for (unsigned i = 0; i < numIssueSlots; i++)
849 DEBUG(std::cerr << "\t#");
850 DEBUG(std::cerr << "\n");
851 for (unsigned i = 0; i < schedule.size(); i++) {
852 DEBUG(std::cerr << "cycle" << i << ": ");
853 for (unsigned j = 0; j < schedule[i].size(); j++)
854 if (schedule[i][j] != NULL)
855 DEBUG(std::cerr << schedule[i][j]->getNodeId() << "\t");
857 DEBUG(std::cerr << "\t");
858 DEBUG(std::cerr << "\n");
861 DEBUG(std::cerr << "dump coreSchedule:" << "\n");
862 for (unsigned i = 0; i < numIssueSlots; i++)
863 DEBUG(std::cerr << "\t#");
864 DEBUG(std::cerr << "\n");
865 for (unsigned i = 0; i < coreSchedule.size(); i++) {
866 DEBUG(std::cerr << "cycle" << i << ": ");
867 for (unsigned j = 0; j < coreSchedule[i].size(); j++)
868 if (coreSchedule[i][j] != NULL)
869 DEBUG(std::cerr << coreSchedule[i][j]->getNodeId() << "\t");
871 DEBUG(std::cerr << "\t");
872 DEBUG(std::cerr << "\n");
878 //---------------------------------------------------------------------------
879 // Function: ModuloSchedulingPass
882 // Entry point for Modulo Scheduling
883 // Schedules LLVM instruction
885 //---------------------------------------------------------------------------
888 class ModuloSchedulingPass:public FunctionPass {
889 const TargetMachine ⌖
892 ModuloSchedulingPass(const TargetMachine &T):target(T) {}
894 const char *getPassName() const {
895 return "Modulo Scheduling";
898 // getAnalysisUsage - We use LiveVarInfo...
899 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
900 //AU.addRequired(FunctionLiveVarInfo::ID);
901 } bool runOnFunction(Function & F);
903 } // end anonymous namespace
906 bool ModuloSchedulingPass::runOnFunction(Function &F)
908 ModuloSchedGraphSet *graphSet = new ModuloSchedGraphSet(&F, target);
909 ModuloSchedulingSet ModuloSchedulingSet(*graphSet);
915 Pass *createModuloSchedulingPass(const TargetMachine & tgt)
917 return new ModuloSchedulingPass(tgt);