2 //***************************************************************************
9 // 7/23/01 - Vikram Adve - Created
10 //***************************************************************************
12 #include "llvm/CodeGen/InstrScheduling.h"
13 #include "llvm/CodeGen/SchedPriorities.h"
14 #include "llvm/Analysis/LiveVar/BBLiveVar.h"
15 #include "llvm/CodeGen/TargetMachine.h"
16 #include "llvm/CodeGen/MachineInstr.h"
17 #include "llvm/Support/CommandLine.h"
18 #include "llvm/Instruction.h"
23 cl::Enum<enum SchedDebugLevel_t> SchedDebugLevel("dsched", cl::NoFlags,
24 "enable instruction scheduling debugging information",
25 clEnumValN(Sched_NoDebugInfo, "n", "disable debug output"),
26 clEnumValN(Sched_PrintMachineCode, "y", "print machine code after scheduling"),
27 clEnumValN(Sched_PrintSchedTrace, "t", "print trace of scheduling actions"),
28 clEnumValN(Sched_PrintSchedGraphs, "g", "print scheduling graphs"), 0);
31 //************************* Forward Declarations ***************************/
34 class SchedulingManager;
37 static void ForwardListSchedule (SchedulingManager& S);
39 static void RecordSchedule (const BasicBlock* bb,
40 const SchedulingManager& S);
42 static unsigned ChooseOneGroup (SchedulingManager& S);
44 static void MarkSuccessorsReady (SchedulingManager& S,
45 const SchedGraphNode* node);
47 static unsigned FindSlotChoices (SchedulingManager& S,
48 DelaySlotInfo*& getDelaySlotInfo);
50 static void AssignInstructionsToSlots(class SchedulingManager& S,
53 static void ScheduleInstr (class SchedulingManager& S,
54 const SchedGraphNode* node,
58 static bool ViolatesMinimumGap (const SchedulingManager& S,
60 const cycles_t inCycle);
62 static bool ConflictsWithChoices (const SchedulingManager& S,
63 MachineOpCode opCode);
65 static void ChooseInstructionsForDelaySlots(SchedulingManager& S,
69 static bool NodeCanFillDelaySlot (const SchedulingManager& S,
70 const SchedGraphNode* node,
71 const SchedGraphNode* brNode,
72 bool nodeIsPredecessor);
74 static void MarkNodeForDelaySlot (SchedulingManager& S,
76 const SchedGraphNode* brNode,
77 bool nodeIsPredecessor);
79 //************************* Internal Data Types *****************************/
82 //----------------------------------------------------------------------
85 // Represents a group of instructions scheduled to be issued
87 //----------------------------------------------------------------------
89 class InstrGroup: public NonCopyable {
91 inline const SchedGraphNode* operator[](unsigned int slotNum) const {
92 assert(slotNum < group.size());
93 return group[slotNum];
97 friend class InstrSchedule;
99 inline void addInstr(const SchedGraphNode* node, unsigned int slotNum) {
100 assert(slotNum < group.size());
101 group[slotNum] = node;
104 /*ctor*/ InstrGroup(unsigned int nslots)
105 : group(nslots, NULL) {}
107 /*ctor*/ InstrGroup(); // disable: DO NOT IMPLEMENT
110 vector<const SchedGraphNode*> group;
114 //----------------------------------------------------------------------
115 // class ScheduleIterator:
117 // Iterates over the machine instructions in the for a single basic block.
118 // The schedule is represented by an InstrSchedule object.
119 //----------------------------------------------------------------------
121 template<class _NodeType>
122 class ScheduleIterator: public std::forward_iterator<_NodeType, ptrdiff_t> {
126 const InstrSchedule& S;
128 typedef ScheduleIterator<_NodeType> _Self;
130 /*ctor*/ inline ScheduleIterator(const InstrSchedule& _schedule,
133 : cycleNum(_cycleNum), slotNum(_slotNum), S(_schedule) {
137 /*ctor*/ inline ScheduleIterator(const _Self& x)
138 : cycleNum(x.cycleNum), slotNum(x.slotNum), S(x.S) {}
140 inline bool operator==(const _Self& x) const {
141 return (slotNum == x.slotNum && cycleNum== x.cycleNum && &S==&x.S);
144 inline bool operator!=(const _Self& x) const { return !operator==(x); }
146 inline _NodeType* operator*() const {
147 assert(cycleNum < S.groups.size());
148 return (*S.groups[cycleNum])[slotNum];
150 inline _NodeType* operator->() const { return operator*(); }
152 _Self& operator++(); // Preincrement
153 inline _Self operator++(int) { // Postincrement
154 _Self tmp(*this); ++*this; return tmp;
157 static _Self begin(const InstrSchedule& _schedule);
158 static _Self end( const InstrSchedule& _schedule);
161 inline _Self& operator=(const _Self& x); // DISABLE -- DO NOT IMPLEMENT
162 void skipToNextInstr();
166 //----------------------------------------------------------------------
167 // class InstrSchedule:
169 // Represents the schedule of machine instructions for a single basic block.
170 //----------------------------------------------------------------------
172 class InstrSchedule: public NonCopyable {
174 const unsigned int nslots;
175 unsigned int numInstr;
176 vector<InstrGroup*> groups; // indexed by cycle number
177 vector<cycles_t> startTime; // indexed by node id
180 typedef ScheduleIterator<SchedGraphNode> iterator;
181 typedef ScheduleIterator<const SchedGraphNode> const_iterator;
184 const_iterator begin() const;
186 const_iterator end() const;
188 public: // constructors and destructor
189 /*ctor*/ InstrSchedule (unsigned int _nslots,
190 unsigned int _numNodes);
191 /*dtor*/ ~InstrSchedule ();
193 public: // accessor functions to query chosen schedule
194 const SchedGraphNode* getInstr (unsigned int slotNum,
196 const InstrGroup* igroup = this->getIGroup(c);
197 return (igroup == NULL)? NULL : (*igroup)[slotNum];
200 inline InstrGroup* getIGroup (cycles_t c) {
201 if (c >= groups.size())
203 if (groups[c] == NULL)
204 groups[c] = new InstrGroup(nslots);
208 inline const InstrGroup* getIGroup (cycles_t c) const {
209 assert(c < groups.size());
213 inline cycles_t getStartTime (unsigned int nodeId) const {
214 assert(nodeId < startTime.size());
215 return startTime[nodeId];
218 unsigned int getNumInstructions() const {
222 inline void scheduleInstr (const SchedGraphNode* node,
223 unsigned int slotNum,
225 InstrGroup* igroup = this->getIGroup(cycle);
226 assert((*igroup)[slotNum] == NULL && "Slot already filled?");
227 igroup->addInstr(node, slotNum);
228 assert(node->getNodeId() < startTime.size());
229 startTime[node->getNodeId()] = cycle;
234 friend class iterator;
235 friend class const_iterator;
236 /*ctor*/ InstrSchedule (); // Disable: DO NOT IMPLEMENT.
241 InstrSchedule::InstrSchedule(unsigned int _nslots, unsigned int _numNodes)
244 groups(2 * _numNodes / _nslots), // 2 x lower-bound for #cycles
245 startTime(_numNodes, (cycles_t) -1) // set all to -1
251 InstrSchedule::~InstrSchedule()
253 for (unsigned c=0, NC=groups.size(); c < NC; c++)
254 if (groups[c] != NULL)
255 delete groups[c]; // delete InstrGroup objects
259 template<class _NodeType>
262 ScheduleIterator<_NodeType>::skipToNextInstr()
264 while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
265 ++cycleNum; // skip cycles with no instructions
267 while (cycleNum < S.groups.size() &&
268 (*S.groups[cycleNum])[slotNum] == NULL)
271 if (slotNum == S.nslots)
275 while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
276 ++cycleNum; // skip cycles with no instructions
281 template<class _NodeType>
283 ScheduleIterator<_NodeType>&
284 ScheduleIterator<_NodeType>::operator++() // Preincrement
287 if (slotNum == S.nslots)
296 template<class _NodeType>
297 ScheduleIterator<_NodeType>
298 ScheduleIterator<_NodeType>::begin(const InstrSchedule& _schedule)
300 return _Self(_schedule, 0, 0);
303 template<class _NodeType>
304 ScheduleIterator<_NodeType>
305 ScheduleIterator<_NodeType>::end(const InstrSchedule& _schedule)
307 return _Self(_schedule, _schedule.groups.size(), 0);
310 InstrSchedule::iterator
311 InstrSchedule::begin()
313 return iterator::begin(*this);
316 InstrSchedule::const_iterator
317 InstrSchedule::begin() const
319 return const_iterator::begin(*this);
322 InstrSchedule::iterator
325 return iterator::end(*this);
328 InstrSchedule::const_iterator
329 InstrSchedule::end() const
331 return const_iterator::end( *this);
335 //----------------------------------------------------------------------
336 // class DelaySlotInfo:
338 // Record information about delay slots for a single branch instruction.
339 // Delay slots are simply indexed by slot number 1 ... numDelaySlots
340 //----------------------------------------------------------------------
342 class DelaySlotInfo: public NonCopyable {
344 const SchedGraphNode* brNode;
345 unsigned int ndelays;
346 vector<const SchedGraphNode*> delayNodeVec;
347 cycles_t delayedNodeCycle;
348 unsigned int delayedNodeSlotNum;
351 /*ctor*/ DelaySlotInfo (const SchedGraphNode* _brNode,
353 : brNode(_brNode), ndelays(_ndelays),
354 delayedNodeCycle(0), delayedNodeSlotNum(0) {}
356 inline unsigned getNumDelays () {
360 inline const vector<const SchedGraphNode*>& getDelayNodeVec() {
364 inline void addDelayNode (const SchedGraphNode* node) {
365 delayNodeVec.push_back(node);
366 assert(delayNodeVec.size() <= ndelays && "Too many delay slot instrs!");
369 inline void recordChosenSlot (cycles_t cycle, unsigned slotNum) {
370 delayedNodeCycle = cycle;
371 delayedNodeSlotNum = slotNum;
374 void scheduleDelayedNode (SchedulingManager& S);
378 //----------------------------------------------------------------------
379 // class SchedulingManager:
381 // Represents the schedule of machine instructions for a single basic block.
382 //----------------------------------------------------------------------
384 class SchedulingManager: public NonCopyable {
385 public: // publicly accessible data members
386 const unsigned int nslots;
387 const MachineSchedInfo& schedInfo;
388 SchedPriorities& schedPrio;
389 InstrSchedule isched;
392 unsigned int totalInstrCount;
394 cycles_t nextEarliestIssueTime; // next cycle we can issue
395 vector<hash_set<const SchedGraphNode*> > choicesForSlot; // indexed by slot#
396 vector<const SchedGraphNode*> choiceVec; // indexed by node ptr
397 vector<int> numInClass; // indexed by sched class
398 vector<cycles_t> nextEarliestStartTime; // indexed by opCode
399 hash_map<const SchedGraphNode*, DelaySlotInfo*> delaySlotInfoForBranches;
400 // indexed by branch node ptr
403 /*ctor*/ SchedulingManager (const TargetMachine& _target,
404 const SchedGraph* graph,
405 SchedPriorities& schedPrio);
406 /*dtor*/ ~SchedulingManager () {}
408 //----------------------------------------------------------------------
409 // Simplify access to the machine instruction info
410 //----------------------------------------------------------------------
412 inline const MachineInstrInfo& getInstrInfo () const {
413 return schedInfo.getInstrInfo();
416 //----------------------------------------------------------------------
417 // Interface for checking and updating the current time
418 //----------------------------------------------------------------------
420 inline cycles_t getTime () const {
424 inline cycles_t getEarliestIssueTime() const {
425 return nextEarliestIssueTime;
428 inline cycles_t getEarliestStartTimeForOp(MachineOpCode opCode) const {
429 assert(opCode < (int) nextEarliestStartTime.size());
430 return nextEarliestStartTime[opCode];
433 // Update current time to specified cycle
434 inline void updateTime (cycles_t c) {
436 schedPrio.updateTime(c);
439 //----------------------------------------------------------------------
440 // Functions to manage the choices for the current cycle including:
441 // -- a vector of choices by priority (choiceVec)
442 // -- vectors of the choices for each instruction slot (choicesForSlot[])
443 // -- number of choices in each sched class, used to check issue conflicts
444 // between choices for a single cycle
445 //----------------------------------------------------------------------
447 inline unsigned int getNumChoices () const {
448 return choiceVec.size();
451 inline unsigned getNumChoicesInClass (const InstrSchedClass& sc) const {
452 assert(sc < (int) numInClass.size() && "Invalid op code or sched class!");
453 return numInClass[sc];
456 inline const SchedGraphNode* getChoice(unsigned int i) const {
457 // assert(i < choiceVec.size()); don't check here.
461 inline hash_set<const SchedGraphNode*>& getChoicesForSlot(unsigned slotNum) {
462 assert(slotNum < nslots);
463 return choicesForSlot[slotNum];
466 inline void addChoice (const SchedGraphNode* node) {
467 // Append the instruction to the vector of choices for current cycle.
468 // Increment numInClass[c] for the sched class to which the instr belongs.
469 choiceVec.push_back(node);
470 const InstrSchedClass& sc = schedInfo.getSchedClass(node->getMachineInstr()->getOpCode());
471 assert(sc < (int) numInClass.size());
475 inline void addChoiceToSlot (unsigned int slotNum,
476 const SchedGraphNode* node) {
477 // Add the instruction to the choice set for the specified slot
478 assert(slotNum < nslots);
479 choicesForSlot[slotNum].insert(node);
482 inline void resetChoices () {
484 for (unsigned int s=0; s < nslots; s++)
485 choicesForSlot[s].clear();
486 for (unsigned int c=0; c < numInClass.size(); c++)
490 //----------------------------------------------------------------------
491 // Code to query and manage the partial instruction schedule so far
492 //----------------------------------------------------------------------
494 inline unsigned int getNumScheduled () const {
495 return isched.getNumInstructions();
498 inline unsigned int getNumUnscheduled() const {
499 return totalInstrCount - isched.getNumInstructions();
502 inline bool isScheduled (const SchedGraphNode* node) const {
503 return (isched.getStartTime(node->getNodeId()) >= 0);
506 inline void scheduleInstr (const SchedGraphNode* node,
507 unsigned int slotNum,
510 assert(! isScheduled(node) && "Instruction already scheduled?");
512 // add the instruction to the schedule
513 isched.scheduleInstr(node, slotNum, cycle);
515 // update the earliest start times of all nodes that conflict with `node'
516 // and the next-earliest time anything can issue if `node' causes bubbles
517 updateEarliestStartTimes(node, cycle);
519 // remove the instruction from the choice sets for all slots
520 for (unsigned s=0; s < nslots; s++)
521 choicesForSlot[s].erase(node);
523 // and decrement the instr count for the sched class to which it belongs
524 const InstrSchedClass& sc = schedInfo.getSchedClass(node->getMachineInstr()->getOpCode());
525 assert(sc < (int) numInClass.size());
529 //----------------------------------------------------------------------
530 // Create and retrieve delay slot info for delayed instructions
531 //----------------------------------------------------------------------
533 inline DelaySlotInfo* getDelaySlotInfoForInstr(const SchedGraphNode* bn,
534 bool createIfMissing=false)
536 DelaySlotInfo* dinfo;
537 hash_map<const SchedGraphNode*, DelaySlotInfo* >::const_iterator
538 I = delaySlotInfoForBranches.find(bn);
539 if (I == delaySlotInfoForBranches.end())
543 dinfo = new DelaySlotInfo(bn,
544 getInstrInfo().getNumDelaySlots(bn->getMachineInstr()->getOpCode()));
545 delaySlotInfoForBranches[bn] = dinfo;
557 /*ctor*/ SchedulingManager (); // Disable: DO NOT IMPLEMENT.
558 void updateEarliestStartTimes(const SchedGraphNode* node,
564 SchedulingManager::SchedulingManager(const TargetMachine& target,
565 const SchedGraph* graph,
566 SchedPriorities& _schedPrio)
567 : nslots(target.getSchedInfo().getMaxNumIssueTotal()),
568 schedInfo(target.getSchedInfo()),
569 schedPrio(_schedPrio),
570 isched(nslots, graph->getNumNodes()),
571 totalInstrCount(graph->getNumNodes() - 2),
572 nextEarliestIssueTime(0),
573 choicesForSlot(nslots),
574 numInClass(target.getSchedInfo().getNumSchedClasses(), 0), // set all to 0
575 nextEarliestStartTime(target.getInstrInfo().getNumRealOpCodes(),
576 (cycles_t) 0) // set all to 0
580 // Note that an upper bound on #choices for each slot is = nslots since
581 // we use this vector to hold a feasible set of instructions, and more
582 // would be infeasible. Reserve that much memory since it is probably small.
583 for (unsigned int i=0; i < nslots; i++)
584 choicesForSlot[i].resize(nslots);
589 SchedulingManager::updateEarliestStartTimes(const SchedGraphNode* node,
592 if (schedInfo.numBubblesAfter(node->getMachineInstr()->getOpCode()) > 0)
593 { // Update next earliest time before which *nothing* can issue.
594 nextEarliestIssueTime = max(nextEarliestIssueTime,
595 curTime + 1 + schedInfo.numBubblesAfter(node->getMachineInstr()->getOpCode()));
598 const vector<MachineOpCode>*
599 conflictVec = schedInfo.getConflictList(node->getMachineInstr()->getOpCode());
601 if (conflictVec != NULL)
602 for (unsigned i=0; i < conflictVec->size(); i++)
604 MachineOpCode toOp = (*conflictVec)[i];
605 cycles_t est = schedTime + schedInfo.getMinIssueGap(node->getMachineInstr()->getOpCode(),
607 assert(toOp < (int) nextEarliestStartTime.size());
608 if (nextEarliestStartTime[toOp] < est)
609 nextEarliestStartTime[toOp] = est;
613 //************************* External Functions *****************************/
616 //---------------------------------------------------------------------------
617 // Function: ScheduleInstructionsWithSSA
620 // Entry point for instruction scheduling on SSA form.
621 // Schedules the machine instructions generated by instruction selection.
622 // Assumes that register allocation has not been done, i.e., operands
623 // are still in SSA form.
624 //---------------------------------------------------------------------------
627 ScheduleInstructionsWithSSA(Method* method,
628 const TargetMachine &target)
630 SchedGraphSet graphSet(method, target);
632 if (SchedDebugLevel >= Sched_PrintSchedGraphs)
634 cout << endl << "*** SCHEDULING GRAPHS FOR INSTRUCTION SCHEDULING"
639 for (SchedGraphSet::const_iterator GI=graphSet.begin();
640 GI != graphSet.end(); ++GI)
642 SchedGraph* graph = (*GI).second;
643 const vector<const BasicBlock*>& bbvec = graph->getBasicBlocks();
644 assert(bbvec.size() == 1 && "Cannot schedule multiple basic blocks");
645 const BasicBlock* bb = bbvec[0];
647 if (SchedDebugLevel >= Sched_PrintSchedTrace)
648 cout << endl << "*** TRACE OF INSTRUCTION SCHEDULING OPERATIONS\n\n";
650 SchedPriorities schedPrio(method, graph); // expensive!
651 SchedulingManager S(target, graph, schedPrio);
653 ChooseInstructionsForDelaySlots(S, bb, graph); // modifies graph
655 ForwardListSchedule(S); // computes schedule in S
657 RecordSchedule((*GI).first, S); // records schedule in BB
660 if (SchedDebugLevel >= Sched_PrintMachineCode)
663 << "*** Machine instructions after INSTRUCTION SCHEDULING" << endl;
664 PrintMachineInstructions(method);
667 return false; // no reason to fail yet
671 // Check minimum gap requirements relative to instructions scheduled in
673 // Note that we do not need to consider `nextEarliestIssueTime' here because
674 // that is also captured in the earliest start times for each opcode.
677 ViolatesMinimumGap(const SchedulingManager& S,
678 MachineOpCode opCode,
679 const cycles_t inCycle)
681 return (inCycle < S.getEarliestStartTimeForOp(opCode));
685 // Check if the instruction would conflict with instructions already
686 // chosen for the current cycle
689 ConflictsWithChoices(const SchedulingManager& S,
690 MachineOpCode opCode)
692 // Check if the instruction must issue by itself, and some feasible
693 // choices have already been made for this cycle
694 if (S.getNumChoices() > 0 && S.schedInfo.isSingleIssue(opCode))
697 // For each class that opCode belongs to, check if there are too many
698 // instructions of that class.
700 const InstrSchedClass sc = S.schedInfo.getSchedClass(opCode);
701 return (S.getNumChoicesInClass(sc) == S.schedInfo.getMaxIssueForClass(sc));
705 // Check if any issue restrictions would prevent the instruction from
706 // being issued in the current cycle
709 instrIsFeasible(const SchedulingManager& S,
710 MachineOpCode opCode)
712 // skip the instruction if it cannot be issued due to issue restrictions
713 // caused by previously issued instructions
714 if (ViolatesMinimumGap(S, opCode, S.getTime()))
717 // skip the instruction if it cannot be issued due to issue restrictions
718 // caused by previously chosen instructions for the current cycle
719 if (ConflictsWithChoices(S, opCode))
725 //************************* Internal Functions *****************************/
729 ForwardListSchedule(SchedulingManager& S)
732 const SchedGraphNode* node;
734 S.schedPrio.initialize();
736 while ((N = S.schedPrio.getNumReady()) > 0)
738 // Choose one group of instructions for a cycle. This will
739 // advance S.getTime() to the first cycle instructions can be issued.
740 // It may also schedule delay slot instructions in later cycles,
741 // but those are ignored here because they are outside the graph.
743 unsigned numIssued = ChooseOneGroup(S);
744 assert(numIssued > 0 && "Deadlock in list scheduling algorithm?");
746 // Notify the priority manager of scheduled instructions and mark
747 // any successors that may now be ready
749 const InstrGroup* igroup = S.isched.getIGroup(S.getTime());
750 for (unsigned int s=0; s < S.nslots; s++)
751 if ((node = (*igroup)[s]) != NULL)
753 S.schedPrio.issuedReadyNodeAt(S.getTime(), node);
754 MarkSuccessorsReady(S, node);
757 // Move to the next the next earliest cycle for which
758 // an instruction can be issued, or the next earliest in which
759 // one will be ready, or to the next cycle, whichever is latest.
761 S.updateTime(max(S.getTime() + 1,
762 max(S.getEarliestIssueTime(),
763 S.schedPrio.getEarliestReadyTime())));
769 // For now, just assume we are scheduling within a single basic block.
770 // Get the machine instruction vector for the basic block and clear it,
771 // then append instructions in scheduled order.
772 // Also, re-insert the dummy PHI instructions that were at the beginning
773 // of the basic block, since they are not part of the schedule.
776 RecordSchedule(const BasicBlock* bb, const SchedulingManager& S)
778 if (S.isched.getNumInstructions() == 0)
779 return; // empty basic block!
781 MachineCodeForBasicBlock& mvec = bb->getMachineInstrVec();
782 unsigned int oldSize = mvec.size();
784 // First find the dummy instructions at the start of the basic block
785 const MachineInstrInfo& mii = S.schedInfo.getInstrInfo();
786 MachineCodeForBasicBlock::iterator I = mvec.begin();
787 for ( ; I != mvec.end(); ++I)
788 if (! mii.isDummyPhiInstr((*I)->getOpCode()))
791 // Erase all except the dummy PHI instructions from mvec, and
792 // pre-allocate create space for the ones we will be put back in.
793 mvec.erase(I, mvec.end());
794 mvec.reserve(mvec.size() + S.isched.getNumInstructions());
796 InstrSchedule::const_iterator NIend = S.isched.end();
797 for (InstrSchedule::const_iterator NI = S.isched.begin(); NI != NIend; ++NI)
798 mvec.push_back(const_cast<MachineInstr*>((*NI)->getMachineInstr()));
803 ChooseOneGroup(SchedulingManager& S)
805 assert(S.schedPrio.getNumReady() > 0
806 && "Don't get here without ready instructions.");
808 DelaySlotInfo* getDelaySlotInfo;
810 // Choose up to `nslots' feasible instructions and their possible slots.
811 unsigned numIssued = FindSlotChoices(S, getDelaySlotInfo);
813 while (numIssued == 0)
815 S.updateTime(S.getTime()+1);
816 numIssued = FindSlotChoices(S, getDelaySlotInfo);
819 AssignInstructionsToSlots(S, numIssued);
821 if (getDelaySlotInfo != NULL)
822 getDelaySlotInfo->scheduleDelayedNode(S);
824 // Print trace of scheduled instructions before newly ready ones
825 if (SchedDebugLevel >= Sched_PrintSchedTrace)
827 cout << " Cycle " << S.getTime() << " : Scheduled instructions:\n";
828 const InstrGroup* igroup = S.isched.getIGroup(S.getTime());
829 for (unsigned int s=0; s < S.nslots; s++)
832 if ((*igroup)[s] != NULL)
833 cout << * ((*igroup)[s])->getMachineInstr() << endl;
835 cout << "<none>" << endl;
844 MarkSuccessorsReady(SchedulingManager& S, const SchedGraphNode* node)
846 // Check if any successors are now ready that were not already marked
847 // ready before, and that have not yet been scheduled.
849 for (sg_succ_const_iterator SI = succ_begin(node); SI !=succ_end(node); ++SI)
850 if (! (*SI)->isDummyNode()
851 && ! S.isScheduled(*SI)
852 && ! S.schedPrio.nodeIsReady(*SI))
853 {// successor not scheduled and not marked ready; check *its* preds.
855 bool succIsReady = true;
856 for (sg_pred_const_iterator P=pred_begin(*SI); P != pred_end(*SI); ++P)
857 if (! (*P)->isDummyNode()
858 && ! S.isScheduled(*P))
864 if (succIsReady) // add the successor to the ready list
865 S.schedPrio.insertReady(*SI);
870 // Choose up to `nslots' FEASIBLE instructions and assign each
871 // instruction to all possible slots that do not violate feasibility.
872 // FEASIBLE means it should be guaranteed that the set
873 // of chosen instructions can be issued in a single group.
876 // maxIssue : total number of feasible instructions
877 // S.choicesForSlot[i=0..nslots] : set of instructions feasible in slot i
880 FindSlotChoices(SchedulingManager& S,
881 DelaySlotInfo*& getDelaySlotInfo)
883 // initialize result vectors to empty
886 // find the slot to start from, in the current cycle
887 unsigned int startSlot = 0;
888 InstrGroup* igroup = S.isched.getIGroup(S.getTime());
889 for (int s = S.nslots - 1; s >= 0; s--)
890 if ((*igroup)[s] != NULL)
896 // Make sure we pick at most one instruction that would break the group.
897 // Also, if we do pick one, remember which it was.
898 unsigned int indexForBreakingNode = S.nslots;
899 unsigned int indexForDelayedInstr = S.nslots;
900 DelaySlotInfo* delaySlotInfo = NULL;
902 getDelaySlotInfo = NULL;
904 // Choose instructions in order of priority.
905 // Add choices to the choice vector in the SchedulingManager class as
906 // we choose them so that subsequent choices will be correctly tested
907 // for feasibility, w.r.t. higher priority choices for the same cycle.
909 while (S.getNumChoices() < S.nslots - startSlot)
911 const SchedGraphNode* nextNode=S.schedPrio.getNextHighest(S,S.getTime());
912 if (nextNode == NULL)
913 break; // no more instructions for this cycle
915 if (S.getInstrInfo().getNumDelaySlots(nextNode->getMachineInstr()->getOpCode()) > 0)
917 delaySlotInfo = S.getDelaySlotInfoForInstr(nextNode);
918 if (delaySlotInfo != NULL)
920 if (indexForBreakingNode < S.nslots)
921 // cannot issue a delayed instr in the same cycle as one
922 // that breaks the issue group or as another delayed instr
925 indexForDelayedInstr = S.getNumChoices();
928 else if (S.schedInfo.breaksIssueGroup(nextNode->getMachineInstr()->getOpCode()))
930 if (indexForBreakingNode < S.nslots)
931 // have a breaking instruction already so throw this one away
934 indexForBreakingNode = S.getNumChoices();
937 if (nextNode != NULL)
938 S.addChoice(nextNode);
940 if (S.schedInfo.isSingleIssue(nextNode->getMachineInstr()->getOpCode()))
942 assert(S.getNumChoices() == 1 &&
943 "Prioritizer returned invalid instr for this cycle!");
947 if (indexForDelayedInstr < S.nslots)
948 break; // leave the rest for delay slots
951 assert(S.getNumChoices() <= S.nslots);
952 assert(! (indexForDelayedInstr < S.nslots &&
953 indexForBreakingNode < S.nslots) && "Cannot have both in a cycle");
955 // Assign each chosen instruction to all possible slots for that instr.
956 // But if only one instruction was chosen, put it only in the first
957 // feasible slot; no more analysis will be needed.
959 if (indexForDelayedInstr >= S.nslots &&
960 indexForBreakingNode >= S.nslots)
961 { // No instructions that break the issue group or that have delay slots.
962 // This is the common case, so handle it separately for efficiency.
964 if (S.getNumChoices() == 1)
966 MachineOpCode opCode = S.getChoice(0)->getMachineInstr()->getOpCode();
968 for (s=startSlot; s < S.nslots; s++)
969 if (S.schedInfo.instrCanUseSlot(opCode, s))
971 assert(s < S.nslots && "No feasible slot for this opCode?");
972 S.addChoiceToSlot(s, S.getChoice(0));
976 for (unsigned i=0; i < S.getNumChoices(); i++)
978 MachineOpCode opCode = S.getChoice(i)->getMachineInstr()->getOpCode();
979 for (unsigned int s=startSlot; s < S.nslots; s++)
980 if (S.schedInfo.instrCanUseSlot(opCode, s))
981 S.addChoiceToSlot(s, S.getChoice(i));
985 else if (indexForDelayedInstr < S.nslots)
987 // There is an instruction that needs delay slots.
988 // Try to assign that instruction to a higher slot than any other
989 // instructions in the group, so that its delay slots can go
993 assert(indexForDelayedInstr == S.getNumChoices() - 1 &&
994 "Instruction with delay slots should be last choice!");
995 assert(delaySlotInfo != NULL && "No delay slot info for instr?");
997 const SchedGraphNode* delayedNode = S.getChoice(indexForDelayedInstr);
998 MachineOpCode delayOpCode = delayedNode->getMachineInstr()->getOpCode();
999 unsigned ndelays= S.getInstrInfo().getNumDelaySlots(delayOpCode);
1001 unsigned delayedNodeSlot = S.nslots;
1002 int highestSlotUsed;
1004 // Find the last possible slot for the delayed instruction that leaves
1005 // at least `d' slots vacant after it (d = #delay slots)
1006 for (int s = S.nslots-ndelays-1; s >= (int) startSlot; s--)
1007 if (S.schedInfo.instrCanUseSlot(delayOpCode, s))
1009 delayedNodeSlot = s;
1013 highestSlotUsed = -1;
1014 for (unsigned i=0; i < S.getNumChoices() - 1; i++)
1016 // Try to assign every other instruction to a lower numbered
1017 // slot than delayedNodeSlot.
1018 MachineOpCode opCode = S.getChoice(i)->getMachineInstr()->getOpCode();
1019 bool noSlotFound = true;
1021 for (s=startSlot; s < delayedNodeSlot; s++)
1022 if (S.schedInfo.instrCanUseSlot(opCode, s))
1024 S.addChoiceToSlot(s, S.getChoice(i));
1025 noSlotFound = false;
1028 // No slot before `delayedNodeSlot' was found for this opCode
1029 // Use a later slot, and allow some delay slots to fall in
1032 for ( ; s < S.nslots; s++)
1033 if (S.schedInfo.instrCanUseSlot(opCode, s))
1035 S.addChoiceToSlot(s, S.getChoice(i));
1039 assert(s < S.nslots && "No feasible slot for instruction?");
1041 highestSlotUsed = max(highestSlotUsed, (int) s);
1044 assert(highestSlotUsed <= (int) S.nslots-1 && "Invalid slot used?");
1046 // We will put the delayed node in the first slot after the
1047 // highest slot used. But we just mark that for now, and
1048 // schedule it separately because we want to schedule the delay
1049 // slots for the node at the same time.
1050 cycles_t dcycle = S.getTime();
1051 unsigned int dslot = highestSlotUsed + 1;
1052 if (dslot == S.nslots)
1057 delaySlotInfo->recordChosenSlot(dcycle, dslot);
1058 getDelaySlotInfo = delaySlotInfo;
1061 { // There is an instruction that breaks the issue group.
1062 // For such an instruction, assign to the last possible slot in
1063 // the current group, and then don't assign any other instructions
1065 assert(indexForBreakingNode < S.nslots);
1066 const SchedGraphNode* breakingNode=S.getChoice(indexForBreakingNode);
1067 unsigned breakingSlot = INT_MAX;
1068 unsigned int nslotsToUse = S.nslots;
1070 // Find the last possible slot for this instruction.
1071 for (int s = S.nslots-1; s >= (int) startSlot; s--)
1072 if (S.schedInfo.instrCanUseSlot(breakingNode->getMachineInstr()->getOpCode(), s))
1077 assert(breakingSlot < S.nslots &&
1078 "No feasible slot for `breakingNode'?");
1080 // Higher priority instructions than the one that breaks the group:
1081 // These can be assigned to all slots, but will be assigned only
1082 // to earlier slots if possible.
1084 i < S.getNumChoices() && i < indexForBreakingNode; i++)
1086 MachineOpCode opCode = S.getChoice(i)->getMachineInstr()->getOpCode();
1088 // If a higher priority instruction cannot be assigned to
1089 // any earlier slots, don't schedule the breaking instruction.
1091 bool foundLowerSlot = false;
1092 nslotsToUse = S.nslots; // May be modified in the loop
1093 for (unsigned int s=startSlot; s < nslotsToUse; s++)
1094 if (S.schedInfo.instrCanUseSlot(opCode, s))
1096 if (breakingSlot < S.nslots && s < breakingSlot)
1098 foundLowerSlot = true;
1099 nslotsToUse = breakingSlot; // RESETS LOOP UPPER BOUND!
1102 S.addChoiceToSlot(s, S.getChoice(i));
1105 if (!foundLowerSlot)
1106 breakingSlot = INT_MAX; // disable breaking instr
1109 // Assign the breaking instruction (if any) to a single slot
1110 // Otherwise, just ignore the instruction. It will simply be
1111 // scheduled in a later cycle.
1112 if (breakingSlot < S.nslots)
1114 S.addChoiceToSlot(breakingSlot, breakingNode);
1115 nslotsToUse = breakingSlot;
1118 nslotsToUse = S.nslots;
1120 // For lower priority instructions than the one that breaks the
1121 // group, only assign them to slots lower than the breaking slot.
1122 // Otherwise, just ignore the instruction.
1123 for (unsigned i=indexForBreakingNode+1; i < S.getNumChoices(); i++)
1125 bool foundLowerSlot = false;
1126 MachineOpCode opCode = S.getChoice(i)->getMachineInstr()->getOpCode();
1127 for (unsigned int s=startSlot; s < nslotsToUse; s++)
1128 if (S.schedInfo.instrCanUseSlot(opCode, s))
1129 S.addChoiceToSlot(s, S.getChoice(i));
1131 } // endif (no delay slots and no breaking slots)
1133 return S.getNumChoices();
1138 AssignInstructionsToSlots(class SchedulingManager& S, unsigned maxIssue)
1140 // find the slot to start from, in the current cycle
1141 unsigned int startSlot = 0;
1142 cycles_t curTime = S.getTime();
1144 assert(maxIssue > 0 && maxIssue <= S.nslots - startSlot);
1146 // If only one instruction can be issued, do so.
1148 for (unsigned s=startSlot; s < S.nslots; s++)
1149 if (S.getChoicesForSlot(s).size() > 0)
1150 {// found the one instruction
1151 S.scheduleInstr(*S.getChoicesForSlot(s).begin(), s, curTime);
1155 // Otherwise, choose from the choices for each slot
1157 InstrGroup* igroup = S.isched.getIGroup(S.getTime());
1158 assert(igroup != NULL && "Group creation failed?");
1160 // Find a slot that has only a single choice, and take it.
1161 // If all slots have 0 or multiple choices, pick the first slot with
1162 // choices and use its last instruction (just to avoid shifting the vector).
1164 for (numIssued = 0; numIssued < maxIssue; numIssued++)
1166 int chosenSlot = -1, chosenNodeIndex = -1;
1167 for (unsigned s=startSlot; s < S.nslots; s++)
1168 if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() == 1)
1170 chosenSlot = (int) s;
1174 if (chosenSlot == -1)
1175 for (unsigned s=startSlot; s < S.nslots; s++)
1176 if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() > 0)
1178 chosenSlot = (int) s;
1182 if (chosenSlot != -1)
1183 { // Insert the chosen instr in the chosen slot and
1184 // erase it from all slots.
1185 const SchedGraphNode* node= *S.getChoicesForSlot(chosenSlot).begin();
1186 S.scheduleInstr(node, chosenSlot, curTime);
1190 assert(numIssued > 0 && "Should not happen when maxIssue > 0!");
1195 //---------------------------------------------------------------------
1196 // Code for filling delay slots for delayed terminator instructions
1197 // (e.g., BRANCH and RETURN). Delay slots for non-terminator
1198 // instructions (e.g., CALL) are not handled here because they almost
1199 // always can be filled with instructions from the call sequence code
1200 // before a call. That's preferable because we incur many tradeoffs here
1201 // when we cannot find single-cycle instructions that can be reordered.
1202 //----------------------------------------------------------------------
1205 ChooseInstructionsForDelaySlots(SchedulingManager& S,
1206 const BasicBlock* bb,
1209 // Look for instructions that can be used for delay slots.
1210 // Remove them from the graph, and mark them to be used for delay slots.
1211 const MachineInstrInfo& mii = S.getInstrInfo();
1212 const TerminatorInst* term = bb->getTerminator();
1213 MachineCodeForVMInstr& termMvec = term->getMachineInstrVec();
1215 // Find the first branch instr in the sequence of machine instrs for term
1218 while (! mii.isBranch(termMvec[first]->getOpCode()))
1220 assert(first < termMvec.size() &&
1221 "No branch instructions for BR? Ok, but weird! Delete assertion.");
1222 if (first == termMvec.size())
1225 SchedGraphNode* brNode = graph->getGraphNodeForInstr(termMvec[first]);
1226 assert(! mii.isCall(brNode->getMachineInstr()->getOpCode()) && "Call used as terminator?");
1228 unsigned ndelays = mii.getNumDelaySlots(brNode->getMachineInstr()->getOpCode());
1232 // Use vectors to remember the nodes chosen for delay slots, and the
1233 // NOPs that will be unused. We cannot remove them from the graph while
1234 // walking through the preds and succs of the brNode here, so we
1235 // remember the nodes in the vectors and remove them later.
1236 // We use separate vectors for the single-cycle and multi-cycle nodes,
1237 // so that we can give preference to single-cycle nodes.
1239 vector<SchedGraphNode*> sdelayNodeVec;
1240 vector<SchedGraphNode*> mdelayNodeVec;
1241 vector<SchedGraphNode*> nopNodeVec;
1242 unsigned numUseful = 0;
1244 sdelayNodeVec.reserve(ndelays);
1246 for (sg_pred_iterator P = pred_begin(brNode);
1247 P != pred_end(brNode) && sdelayNodeVec.size() < ndelays; ++P)
1248 if (! (*P)->isDummyNode() &&
1249 ! mii.isNop((*P)->getMachineInstr()->getOpCode()) &&
1250 NodeCanFillDelaySlot(S, *P, brNode, /*pred*/ true))
1253 if (mii.maxLatency((*P)->getMachineInstr()->getOpCode()) > 1)
1254 mdelayNodeVec.push_back(*P);
1256 sdelayNodeVec.push_back(*P);
1259 // If not enough single-cycle instructions were found, select the
1260 // lowest-latency multi-cycle instructions and use them.
1261 // Note that this is the most efficient code when only 1 (or even 2)
1262 // values need to be selected.
1264 while (sdelayNodeVec.size() < ndelays && mdelayNodeVec.size() > 0)
1267 unsigned minLatency = mii.maxLatency(mdelayNodeVec[0]->getMachineInstr()->getOpCode());
1268 unsigned minIndex = 0;
1269 for (unsigned i=1; i < mdelayNodeVec.size(); i++)
1271 (latency = mii.maxLatency(mdelayNodeVec[i]->getMachineInstr()->getOpCode())))
1273 minLatency = latency;
1276 sdelayNodeVec.push_back(mdelayNodeVec[minIndex]);
1277 if (sdelayNodeVec.size() < ndelays) // avoid the last erase!
1278 mdelayNodeVec.erase(mdelayNodeVec.begin() + minIndex);
1281 // Now, remove the NOPs currently in delay slots from the graph.
1282 // If not enough useful instructions were found, use the NOPs to
1283 // fill delay slots, otherwise, just discard them.
1284 for (sg_succ_iterator I=succ_begin(brNode); I != succ_end(brNode); ++I)
1285 if (! (*I)->isDummyNode()
1286 && mii.isNop((*I)->getMachineInstr()->getOpCode()))
1288 if (sdelayNodeVec.size() < ndelays)
1289 sdelayNodeVec.push_back(*I);
1291 nopNodeVec.push_back(*I);
1294 // Mark the nodes chosen for delay slots. This removes them from the graph.
1295 for (unsigned i=0; i < sdelayNodeVec.size(); i++)
1296 MarkNodeForDelaySlot(S, sdelayNodeVec[i], brNode, true);
1298 // And remove the unused NOPs the graph.
1299 for (unsigned i=0; i < nopNodeVec.size(); i++)
1300 nopNodeVec[i]->eraseAllEdges();
1305 NodeCanFillDelaySlot(const SchedulingManager& S,
1306 const SchedGraphNode* node,
1307 const SchedGraphNode* brNode,
1308 bool nodeIsPredecessor)
1310 assert(! node->isDummyNode());
1312 // don't put a branch in the delay slot of another branch
1313 if (S.getInstrInfo().isBranch(node->getMachineInstr()->getOpCode()))
1316 // don't put a single-issue instruction in the delay slot of a branch
1317 if (S.schedInfo.isSingleIssue(node->getMachineInstr()->getOpCode()))
1320 // don't put a load-use dependence in the delay slot of a branch
1321 const MachineInstrInfo& mii = S.getInstrInfo();
1323 for (SchedGraphNode::const_iterator EI = node->beginInEdges();
1324 EI != node->endInEdges(); ++EI)
1325 if (! (*EI)->getSrc()->isDummyNode()
1326 && mii.isLoad((*EI)->getSrc()->getMachineInstr()->getOpCode())
1327 && (*EI)->getDepType() == SchedGraphEdge::CtrlDep)
1330 // for now, don't put an instruction that does not have operand
1331 // interlocks in the delay slot of a branch
1332 if (! S.getInstrInfo().hasOperandInterlock(node->getMachineInstr()->getOpCode()))
1335 // Finally, if the instruction preceeds the branch, we make sure the
1336 // instruction can be reordered relative to the branch. We simply check
1337 // if the instr. has only 1 outgoing edge, viz., a CD edge to the branch.
1339 if (nodeIsPredecessor)
1341 bool onlyCDEdgeToBranch = true;
1342 for (SchedGraphNode::const_iterator OEI = node->beginOutEdges();
1343 OEI != node->endOutEdges(); ++OEI)
1344 if (! (*OEI)->getSink()->isDummyNode()
1345 && ((*OEI)->getSink() != brNode
1346 || (*OEI)->getDepType() != SchedGraphEdge::CtrlDep))
1348 onlyCDEdgeToBranch = false;
1352 if (!onlyCDEdgeToBranch)
1361 MarkNodeForDelaySlot(SchedulingManager& S,
1362 SchedGraphNode* node,
1363 const SchedGraphNode* brNode,
1364 bool nodeIsPredecessor)
1366 if (nodeIsPredecessor)
1367 { // If node is in the same basic block (i.e., preceeds brNode),
1368 // remove it and all its incident edges from the graph.
1369 node->eraseAllEdges();
1372 { // If the node was from a target block, add the node to the graph
1373 // and add a CD edge from brNode to node.
1374 assert(0 && "NOT IMPLEMENTED YET");
1377 DelaySlotInfo* dinfo = S.getDelaySlotInfoForInstr(brNode, /*create*/ true);
1378 dinfo->addDelayNode(node);
1383 // Schedule the delayed branch and its delay slots
1386 DelaySlotInfo::scheduleDelayedNode(SchedulingManager& S)
1388 assert(delayedNodeSlotNum < S.nslots && "Illegal slot for branch");
1389 assert(S.isched.getInstr(delayedNodeSlotNum, delayedNodeCycle) == NULL
1390 && "Slot for branch should be empty");
1392 unsigned int nextSlot = delayedNodeSlotNum;
1393 cycles_t nextTime = delayedNodeCycle;
1395 S.scheduleInstr(brNode, nextSlot, nextTime);
1397 for (unsigned d=0; d < ndelays; d++)
1400 if (nextSlot == S.nslots)
1406 // Find the first feasible instruction for this delay slot
1407 // Note that we only check for issue restrictions here.
1408 // We do *not* check for flow dependences but rely on pipeline
1409 // interlocks to resolve them. Machines without interlocks
1410 // will require this code to be modified.
1411 for (unsigned i=0; i < delayNodeVec.size(); i++)
1413 const SchedGraphNode* dnode = delayNodeVec[i];
1414 if ( ! S.isScheduled(dnode)
1415 && S.schedInfo.instrCanUseSlot(dnode->getMachineInstr()->getOpCode(), nextSlot)
1416 && instrIsFeasible(S, dnode->getMachineInstr()->getOpCode()))
1418 assert(S.getInstrInfo().hasOperandInterlock(dnode->getMachineInstr()->getOpCode())
1419 && "Instructions without interlocks not yet supported "
1420 "when filling branch delay slots");
1421 S.scheduleInstr(dnode, nextSlot, nextTime);
1427 // Update current time if delay slots overflowed into later cycles.
1428 // Do this here because we know exactly which cycle is the last cycle
1429 // that contains delay slots. The next loop doesn't compute that.
1430 if (nextTime > S.getTime())
1431 S.updateTime(nextTime);
1433 // Now put any remaining instructions in the unfilled delay slots.
1434 // This could lead to suboptimal performance but needed for correctness.
1435 nextSlot = delayedNodeSlotNum;
1436 nextTime = delayedNodeCycle;
1437 for (unsigned i=0; i < delayNodeVec.size(); i++)
1438 if (! S.isScheduled(delayNodeVec[i]))
1440 do { // find the next empty slot
1442 if (nextSlot == S.nslots)
1447 } while (S.isched.getInstr(nextSlot, nextTime) != NULL);
1449 S.scheduleInstr(delayNodeVec[i], nextSlot, nextTime);