2 //***************************************************************************
9 // 7/23/01 - Vikram Adve - Created
10 //**************************************************************************/
13 //************************* User Include Files *****************************/
15 #include "llvm/CodeGen/InstrScheduling.h"
16 #include "SchedPriorities.h"
17 #include "llvm/Analysis/LiveVar/BBLiveVar.h"
18 #include "llvm/CodeGen/MachineInstr.h"
19 #include "llvm/Support/CommandLine.h"
20 #include "llvm/Instruction.h"
23 //************************ System Include Files *****************************/
30 //************************* External Data Types *****************************/
32 cl::Enum<enum SchedDebugLevel_t> SchedDebugLevel("dsched", cl::NoFlags,
33 "enable instruction scheduling debugging information",
34 clEnumValN(Sched_NoDebugInfo, "n", "disable debug output"),
35 clEnumValN(Sched_PrintMachineCode, "y", "print machine code after scheduling"),
36 clEnumValN(Sched_PrintSchedTrace, "t", "print trace of scheduling actions"),
37 clEnumValN(Sched_PrintSchedGraphs, "g", "print scheduling graphs"), 0);
40 //************************* Internal Data Types *****************************/
43 class SchedulingManager;
47 //----------------------------------------------------------------------
50 // Represents a group of instructions scheduled to be issued
52 //----------------------------------------------------------------------
54 class InstrGroup: public NonCopyable {
56 inline const SchedGraphNode* operator[](unsigned int slotNum) const {
57 assert(slotNum < group.size());
58 return group[slotNum];
62 friend class InstrSchedule;
64 inline void addInstr(const SchedGraphNode* node, unsigned int slotNum) {
65 assert(slotNum < group.size());
66 group[slotNum] = node;
69 /*ctor*/ InstrGroup(unsigned int nslots)
70 : group(nslots, NULL) {}
72 /*ctor*/ InstrGroup(); // disable: DO NOT IMPLEMENT
75 vector<const SchedGraphNode*> group;
79 //----------------------------------------------------------------------
80 // class ScheduleIterator:
82 // Iterates over the machine instructions in the for a single basic block.
83 // The schedule is represented by an InstrSchedule object.
84 //----------------------------------------------------------------------
86 template<class _NodeType>
87 class ScheduleIterator: public std::forward_iterator<_NodeType, ptrdiff_t> {
91 const InstrSchedule& S;
93 typedef ScheduleIterator<_NodeType> _Self;
95 /*ctor*/ inline ScheduleIterator(const InstrSchedule& _schedule,
98 : cycleNum(_cycleNum), slotNum(_slotNum), S(_schedule) {
102 /*ctor*/ inline ScheduleIterator(const _Self& x)
103 : cycleNum(x.cycleNum), slotNum(x.slotNum), S(x.S) {}
105 inline bool operator==(const _Self& x) const {
106 return (slotNum == x.slotNum && cycleNum== x.cycleNum && &S==&x.S);
109 inline bool operator!=(const _Self& x) const { return !operator==(x); }
111 inline _NodeType* operator*() const {
112 assert(cycleNum < S.groups.size());
113 return (*S.groups[cycleNum])[slotNum];
115 inline _NodeType* operator->() const { return operator*(); }
117 _Self& operator++(); // Preincrement
118 inline _Self operator++(int) { // Postincrement
119 _Self tmp(*this); ++*this; return tmp;
122 static _Self begin(const InstrSchedule& _schedule);
123 static _Self end( const InstrSchedule& _schedule);
126 inline _Self& operator=(const _Self& x); // DISABLE -- DO NOT IMPLEMENT
127 void skipToNextInstr();
131 //----------------------------------------------------------------------
132 // class InstrSchedule:
134 // Represents the schedule of machine instructions for a single basic block.
135 //----------------------------------------------------------------------
137 class InstrSchedule: public NonCopyable {
139 const unsigned int nslots;
140 unsigned int numInstr;
141 vector<InstrGroup*> groups; // indexed by cycle number
142 vector<cycles_t> startTime; // indexed by node id
145 typedef ScheduleIterator<SchedGraphNode> iterator;
146 typedef ScheduleIterator<const SchedGraphNode> const_iterator;
149 const_iterator begin() const;
151 const_iterator end() const;
153 public: // constructors and destructor
154 /*ctor*/ InstrSchedule (unsigned int _nslots,
155 unsigned int _numNodes);
156 /*dtor*/ ~InstrSchedule ();
158 public: // accessor functions to query chosen schedule
159 const SchedGraphNode* getInstr (unsigned int slotNum,
161 const InstrGroup* igroup = this->getIGroup(c);
162 return (igroup == NULL)? NULL : (*igroup)[slotNum];
165 inline InstrGroup* getIGroup (cycles_t c) {
166 if (c >= groups.size())
168 if (groups[c] == NULL)
169 groups[c] = new InstrGroup(nslots);
173 inline const InstrGroup* getIGroup (cycles_t c) const {
174 assert(c < groups.size());
178 inline cycles_t getStartTime (unsigned int nodeId) const {
179 assert(nodeId < startTime.size());
180 return startTime[nodeId];
183 unsigned int getNumInstructions() const {
187 inline void scheduleInstr (const SchedGraphNode* node,
188 unsigned int slotNum,
190 InstrGroup* igroup = this->getIGroup(cycle);
191 assert((*igroup)[slotNum] == NULL && "Slot already filled?");
192 igroup->addInstr(node, slotNum);
193 assert(node->getNodeId() < startTime.size());
194 startTime[node->getNodeId()] = cycle;
199 friend class iterator;
200 friend class const_iterator;
201 /*ctor*/ InstrSchedule (); // Disable: DO NOT IMPLEMENT.
206 InstrSchedule::InstrSchedule(unsigned int _nslots, unsigned int _numNodes)
209 groups(2 * _numNodes / _nslots), // 2 x lower-bound for #cycles
210 startTime(_numNodes, (cycles_t) -1) // set all to -1
216 InstrSchedule::~InstrSchedule()
218 for (unsigned c=0, NC=groups.size(); c < NC; c++)
219 if (groups[c] != NULL)
220 delete groups[c]; // delete InstrGroup objects
224 template<class _NodeType>
227 ScheduleIterator<_NodeType>::skipToNextInstr()
229 while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
230 ++cycleNum; // skip cycles with no instructions
232 while (cycleNum < S.groups.size() &&
233 (*S.groups[cycleNum])[slotNum] == NULL)
236 if (slotNum == S.nslots)
240 while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
241 ++cycleNum; // skip cycles with no instructions
246 template<class _NodeType>
248 ScheduleIterator<_NodeType>&
249 ScheduleIterator<_NodeType>::operator++() // Preincrement
252 if (slotNum == S.nslots)
261 template<class _NodeType>
262 ScheduleIterator<_NodeType>
263 ScheduleIterator<_NodeType>::begin(const InstrSchedule& _schedule)
265 return _Self(_schedule, 0, 0);
268 template<class _NodeType>
269 ScheduleIterator<_NodeType>
270 ScheduleIterator<_NodeType>::end(const InstrSchedule& _schedule)
272 return _Self(_schedule, _schedule.groups.size(), 0);
275 InstrSchedule::iterator
276 InstrSchedule::begin()
278 return iterator::begin(*this);
281 InstrSchedule::const_iterator
282 InstrSchedule::begin() const
284 return const_iterator::begin(*this);
287 InstrSchedule::iterator
290 return iterator::end(*this);
293 InstrSchedule::const_iterator
294 InstrSchedule::end() const
296 return const_iterator::end( *this);
300 //----------------------------------------------------------------------
301 // class DelaySlotInfo:
303 // Record information about delay slots for a single branch instruction.
304 // Delay slots are simply indexed by slot number 1 ... numDelaySlots
305 //----------------------------------------------------------------------
307 class DelaySlotInfo: public NonCopyable {
309 const SchedGraphNode* brNode;
310 unsigned int ndelays;
311 vector<const SchedGraphNode*> delayNodeVec;
312 cycles_t delayedNodeCycle;
313 unsigned int delayedNodeSlotNum;
316 /*ctor*/ DelaySlotInfo (const SchedGraphNode* _brNode,
318 : brNode(_brNode), ndelays(_ndelays),
319 delayedNodeCycle(0), delayedNodeSlotNum(0) {}
321 inline unsigned getNumDelays () {
325 inline const vector<const SchedGraphNode*>& getDelayNodeVec() {
329 inline void addDelayNode (const SchedGraphNode* node) {
330 delayNodeVec.push_back(node);
331 assert(delayNodeVec.size() <= ndelays && "Too many delay slot instrs!");
334 inline void recordChosenSlot (cycles_t cycle, unsigned slotNum) {
335 delayedNodeCycle = cycle;
336 delayedNodeSlotNum = slotNum;
339 unsigned scheduleDelayedNode (SchedulingManager& S);
343 //----------------------------------------------------------------------
344 // class SchedulingManager:
346 // Represents the schedule of machine instructions for a single basic block.
347 //----------------------------------------------------------------------
349 class SchedulingManager: public NonCopyable {
350 public: // publicly accessible data members
351 const unsigned int nslots;
352 const MachineSchedInfo& schedInfo;
353 SchedPriorities& schedPrio;
354 InstrSchedule isched;
357 unsigned int totalInstrCount;
359 cycles_t nextEarliestIssueTime; // next cycle we can issue
360 vector<hash_set<const SchedGraphNode*> > choicesForSlot; // indexed by slot#
361 vector<const SchedGraphNode*> choiceVec; // indexed by node ptr
362 vector<int> numInClass; // indexed by sched class
363 vector<cycles_t> nextEarliestStartTime; // indexed by opCode
364 hash_map<const SchedGraphNode*, DelaySlotInfo*> delaySlotInfoForBranches;
365 // indexed by branch node ptr
368 /*ctor*/ SchedulingManager (const TargetMachine& _target,
369 const SchedGraph* graph,
370 SchedPriorities& schedPrio);
371 /*dtor*/ ~SchedulingManager () {}
373 //----------------------------------------------------------------------
374 // Simplify access to the machine instruction info
375 //----------------------------------------------------------------------
377 inline const MachineInstrInfo& getInstrInfo () const {
378 return schedInfo.getInstrInfo();
381 //----------------------------------------------------------------------
382 // Interface for checking and updating the current time
383 //----------------------------------------------------------------------
385 inline cycles_t getTime () const {
389 inline cycles_t getEarliestIssueTime() const {
390 return nextEarliestIssueTime;
393 inline cycles_t getEarliestStartTimeForOp(MachineOpCode opCode) const {
394 assert(opCode < (int) nextEarliestStartTime.size());
395 return nextEarliestStartTime[opCode];
398 // Update current time to specified cycle
399 inline void updateTime (cycles_t c) {
401 schedPrio.updateTime(c);
404 //----------------------------------------------------------------------
405 // Functions to manage the choices for the current cycle including:
406 // -- a vector of choices by priority (choiceVec)
407 // -- vectors of the choices for each instruction slot (choicesForSlot[])
408 // -- number of choices in each sched class, used to check issue conflicts
409 // between choices for a single cycle
410 //----------------------------------------------------------------------
412 inline unsigned int getNumChoices () const {
413 return choiceVec.size();
416 inline unsigned getNumChoicesInClass (const InstrSchedClass& sc) const {
417 assert(sc < (int) numInClass.size() && "Invalid op code or sched class!");
418 return numInClass[sc];
421 inline const SchedGraphNode* getChoice(unsigned int i) const {
422 // assert(i < choiceVec.size()); don't check here.
426 inline hash_set<const SchedGraphNode*>& getChoicesForSlot(unsigned slotNum) {
427 assert(slotNum < nslots);
428 return choicesForSlot[slotNum];
431 inline void addChoice (const SchedGraphNode* node) {
432 // Append the instruction to the vector of choices for current cycle.
433 // Increment numInClass[c] for the sched class to which the instr belongs.
434 choiceVec.push_back(node);
435 const InstrSchedClass& sc = schedInfo.getSchedClass(node->getMachineInstr()->getOpCode());
436 assert(sc < (int) numInClass.size());
440 inline void addChoiceToSlot (unsigned int slotNum,
441 const SchedGraphNode* node) {
442 // Add the instruction to the choice set for the specified slot
443 assert(slotNum < nslots);
444 choicesForSlot[slotNum].insert(node);
447 inline void resetChoices () {
449 for (unsigned int s=0; s < nslots; s++)
450 choicesForSlot[s].clear();
451 for (unsigned int c=0; c < numInClass.size(); c++)
455 //----------------------------------------------------------------------
456 // Code to query and manage the partial instruction schedule so far
457 //----------------------------------------------------------------------
459 inline unsigned int getNumScheduled () const {
460 return isched.getNumInstructions();
463 inline unsigned int getNumUnscheduled() const {
464 return totalInstrCount - isched.getNumInstructions();
467 inline bool isScheduled (const SchedGraphNode* node) const {
468 return (isched.getStartTime(node->getNodeId()) >= 0);
471 inline void scheduleInstr (const SchedGraphNode* node,
472 unsigned int slotNum,
475 assert(! isScheduled(node) && "Instruction already scheduled?");
477 // add the instruction to the schedule
478 isched.scheduleInstr(node, slotNum, cycle);
480 // update the earliest start times of all nodes that conflict with `node'
481 // and the next-earliest time anything can issue if `node' causes bubbles
482 updateEarliestStartTimes(node, cycle);
484 // remove the instruction from the choice sets for all slots
485 for (unsigned s=0; s < nslots; s++)
486 choicesForSlot[s].erase(node);
488 // and decrement the instr count for the sched class to which it belongs
489 const InstrSchedClass& sc = schedInfo.getSchedClass(node->getMachineInstr()->getOpCode());
490 assert(sc < (int) numInClass.size());
494 //----------------------------------------------------------------------
495 // Create and retrieve delay slot info for delayed instructions
496 //----------------------------------------------------------------------
498 inline DelaySlotInfo* getDelaySlotInfoForInstr(const SchedGraphNode* bn,
499 bool createIfMissing=false)
501 DelaySlotInfo* dinfo;
502 hash_map<const SchedGraphNode*, DelaySlotInfo* >::const_iterator
503 I = delaySlotInfoForBranches.find(bn);
504 if (I == delaySlotInfoForBranches.end())
508 dinfo = new DelaySlotInfo(bn,
509 getInstrInfo().getNumDelaySlots(bn->getMachineInstr()->getOpCode()));
510 delaySlotInfoForBranches[bn] = dinfo;
522 /*ctor*/ SchedulingManager (); // Disable: DO NOT IMPLEMENT.
523 void updateEarliestStartTimes(const SchedGraphNode* node,
529 SchedulingManager::SchedulingManager(const TargetMachine& target,
530 const SchedGraph* graph,
531 SchedPriorities& _schedPrio)
532 : nslots(target.getSchedInfo().getMaxNumIssueTotal()),
533 schedInfo(target.getSchedInfo()),
534 schedPrio(_schedPrio),
535 isched(nslots, graph->getNumNodes()),
536 totalInstrCount(graph->getNumNodes() - 2),
537 nextEarliestIssueTime(0),
538 choicesForSlot(nslots),
539 numInClass(target.getSchedInfo().getNumSchedClasses(), 0), // set all to 0
540 nextEarliestStartTime(target.getInstrInfo().getNumRealOpCodes(),
541 (cycles_t) 0) // set all to 0
545 // Note that an upper bound on #choices for each slot is = nslots since
546 // we use this vector to hold a feasible set of instructions, and more
547 // would be infeasible. Reserve that much memory since it is probably small.
548 for (unsigned int i=0; i < nslots; i++)
549 choicesForSlot[i].resize(nslots);
554 SchedulingManager::updateEarliestStartTimes(const SchedGraphNode* node,
557 if (schedInfo.numBubblesAfter(node->getMachineInstr()->getOpCode()) > 0)
558 { // Update next earliest time before which *nothing* can issue.
559 nextEarliestIssueTime = max(nextEarliestIssueTime,
560 curTime + 1 + schedInfo.numBubblesAfter(node->getMachineInstr()->getOpCode()));
563 const vector<MachineOpCode>*
564 conflictVec = schedInfo.getConflictList(node->getMachineInstr()->getOpCode());
566 if (conflictVec != NULL)
567 for (unsigned i=0; i < conflictVec->size(); i++)
569 MachineOpCode toOp = (*conflictVec)[i];
570 cycles_t est = schedTime + schedInfo.getMinIssueGap(node->getMachineInstr()->getOpCode(),
572 assert(toOp < (int) nextEarliestStartTime.size());
573 if (nextEarliestStartTime[toOp] < est)
574 nextEarliestStartTime[toOp] = est;
578 //************************* Internal Functions *****************************/
582 AssignInstructionsToSlots(class SchedulingManager& S, unsigned maxIssue)
584 // find the slot to start from, in the current cycle
585 unsigned int startSlot = 0;
586 cycles_t curTime = S.getTime();
588 assert(maxIssue > 0 && maxIssue <= S.nslots - startSlot);
590 // If only one instruction can be issued, do so.
592 for (unsigned s=startSlot; s < S.nslots; s++)
593 if (S.getChoicesForSlot(s).size() > 0)
594 {// found the one instruction
595 S.scheduleInstr(*S.getChoicesForSlot(s).begin(), s, curTime);
599 // Otherwise, choose from the choices for each slot
601 InstrGroup* igroup = S.isched.getIGroup(S.getTime());
602 assert(igroup != NULL && "Group creation failed?");
604 // Find a slot that has only a single choice, and take it.
605 // If all slots have 0 or multiple choices, pick the first slot with
606 // choices and use its last instruction (just to avoid shifting the vector).
608 for (numIssued = 0; numIssued < maxIssue; numIssued++)
610 int chosenSlot = -1, chosenNodeIndex = -1;
611 for (unsigned s=startSlot; s < S.nslots; s++)
612 if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() == 1)
614 chosenSlot = (int) s;
618 if (chosenSlot == -1)
619 for (unsigned s=startSlot; s < S.nslots; s++)
620 if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() > 0)
622 chosenSlot = (int) s;
626 if (chosenSlot != -1)
627 { // Insert the chosen instr in the chosen slot and
628 // erase it from all slots.
629 const SchedGraphNode* node= *S.getChoicesForSlot(chosenSlot).begin();
630 S.scheduleInstr(node, chosenSlot, curTime);
634 assert(numIssued > 0 && "Should not happen when maxIssue > 0!");
639 // For now, just assume we are scheduling within a single basic block.
640 // Get the machine instruction vector for the basic block and clear it,
641 // then append instructions in scheduled order.
642 // Also, re-insert the dummy PHI instructions that were at the beginning
643 // of the basic block, since they are not part of the schedule.
646 RecordSchedule(const BasicBlock* bb, const SchedulingManager& S)
648 MachineCodeForBasicBlock& mvec = bb->getMachineInstrVec();
649 const MachineInstrInfo& mii = S.schedInfo.getInstrInfo();
652 // Lets make sure we didn't lose any instructions, except possibly
653 // some NOPs from delay slots. Also, PHIs are not included in the schedule.
654 unsigned numInstr = 0;
655 for (MachineCodeForBasicBlock::iterator I=mvec.begin(); I != mvec.end(); ++I)
656 if (! mii.isNop((*I)->getOpCode()) &&
657 ! mii.isDummyPhiInstr((*I)->getOpCode()))
659 assert(S.isched.getNumInstructions() >= numInstr &&
660 "Lost some non-NOP instructions during scheduling!");
663 if (S.isched.getNumInstructions() == 0)
664 return; // empty basic block!
666 // First find the dummy instructions at the start of the basic block
667 MachineCodeForBasicBlock::iterator I = mvec.begin();
668 for ( ; I != mvec.end(); ++I)
669 if (! mii.isDummyPhiInstr((*I)->getOpCode()))
672 // Erase all except the dummy PHI instructions from mvec, and
673 // pre-allocate create space for the ones we will put back in.
674 mvec.erase(I, mvec.end());
675 mvec.reserve(mvec.size() + S.isched.getNumInstructions());
677 InstrSchedule::const_iterator NIend = S.isched.end();
678 for (InstrSchedule::const_iterator NI = S.isched.begin(); NI != NIend; ++NI)
679 mvec.push_back(const_cast<MachineInstr*>((*NI)->getMachineInstr()));
685 MarkSuccessorsReady(SchedulingManager& S, const SchedGraphNode* node)
687 // Check if any successors are now ready that were not already marked
688 // ready before, and that have not yet been scheduled.
690 for (sg_succ_const_iterator SI = succ_begin(node); SI !=succ_end(node); ++SI)
691 if (! (*SI)->isDummyNode()
692 && ! S.isScheduled(*SI)
693 && ! S.schedPrio.nodeIsReady(*SI))
694 {// successor not scheduled and not marked ready; check *its* preds.
696 bool succIsReady = true;
697 for (sg_pred_const_iterator P=pred_begin(*SI); P != pred_end(*SI); ++P)
698 if (! (*P)->isDummyNode()
699 && ! S.isScheduled(*P))
705 if (succIsReady) // add the successor to the ready list
706 S.schedPrio.insertReady(*SI);
711 // Choose up to `nslots' FEASIBLE instructions and assign each
712 // instruction to all possible slots that do not violate feasibility.
713 // FEASIBLE means it should be guaranteed that the set
714 // of chosen instructions can be issued in a single group.
717 // maxIssue : total number of feasible instructions
718 // S.choicesForSlot[i=0..nslots] : set of instructions feasible in slot i
721 FindSlotChoices(SchedulingManager& S,
722 DelaySlotInfo*& getDelaySlotInfo)
724 // initialize result vectors to empty
727 // find the slot to start from, in the current cycle
728 unsigned int startSlot = 0;
729 InstrGroup* igroup = S.isched.getIGroup(S.getTime());
730 for (int s = S.nslots - 1; s >= 0; s--)
731 if ((*igroup)[s] != NULL)
737 // Make sure we pick at most one instruction that would break the group.
738 // Also, if we do pick one, remember which it was.
739 unsigned int indexForBreakingNode = S.nslots;
740 unsigned int indexForDelayedInstr = S.nslots;
741 DelaySlotInfo* delaySlotInfo = NULL;
743 getDelaySlotInfo = NULL;
745 // Choose instructions in order of priority.
746 // Add choices to the choice vector in the SchedulingManager class as
747 // we choose them so that subsequent choices will be correctly tested
748 // for feasibility, w.r.t. higher priority choices for the same cycle.
750 while (S.getNumChoices() < S.nslots - startSlot)
752 const SchedGraphNode* nextNode=S.schedPrio.getNextHighest(S,S.getTime());
753 if (nextNode == NULL)
754 break; // no more instructions for this cycle
756 if (S.getInstrInfo().getNumDelaySlots(nextNode->getMachineInstr()->getOpCode()) > 0)
758 delaySlotInfo = S.getDelaySlotInfoForInstr(nextNode);
759 if (delaySlotInfo != NULL)
761 if (indexForBreakingNode < S.nslots)
762 // cannot issue a delayed instr in the same cycle as one
763 // that breaks the issue group or as another delayed instr
766 indexForDelayedInstr = S.getNumChoices();
769 else if (S.schedInfo.breaksIssueGroup(nextNode->getMachineInstr()->getOpCode()))
771 if (indexForBreakingNode < S.nslots)
772 // have a breaking instruction already so throw this one away
775 indexForBreakingNode = S.getNumChoices();
778 if (nextNode != NULL)
779 S.addChoice(nextNode);
781 if (S.schedInfo.isSingleIssue(nextNode->getMachineInstr()->getOpCode()))
783 assert(S.getNumChoices() == 1 &&
784 "Prioritizer returned invalid instr for this cycle!");
788 if (indexForDelayedInstr < S.nslots)
789 break; // leave the rest for delay slots
792 assert(S.getNumChoices() <= S.nslots);
793 assert(! (indexForDelayedInstr < S.nslots &&
794 indexForBreakingNode < S.nslots) && "Cannot have both in a cycle");
796 // Assign each chosen instruction to all possible slots for that instr.
797 // But if only one instruction was chosen, put it only in the first
798 // feasible slot; no more analysis will be needed.
800 if (indexForDelayedInstr >= S.nslots &&
801 indexForBreakingNode >= S.nslots)
802 { // No instructions that break the issue group or that have delay slots.
803 // This is the common case, so handle it separately for efficiency.
805 if (S.getNumChoices() == 1)
807 MachineOpCode opCode = S.getChoice(0)->getMachineInstr()->getOpCode();
809 for (s=startSlot; s < S.nslots; s++)
810 if (S.schedInfo.instrCanUseSlot(opCode, s))
812 assert(s < S.nslots && "No feasible slot for this opCode?");
813 S.addChoiceToSlot(s, S.getChoice(0));
817 for (unsigned i=0; i < S.getNumChoices(); i++)
819 MachineOpCode opCode = S.getChoice(i)->getMachineInstr()->getOpCode();
820 for (unsigned int s=startSlot; s < S.nslots; s++)
821 if (S.schedInfo.instrCanUseSlot(opCode, s))
822 S.addChoiceToSlot(s, S.getChoice(i));
826 else if (indexForDelayedInstr < S.nslots)
828 // There is an instruction that needs delay slots.
829 // Try to assign that instruction to a higher slot than any other
830 // instructions in the group, so that its delay slots can go
834 assert(indexForDelayedInstr == S.getNumChoices() - 1 &&
835 "Instruction with delay slots should be last choice!");
836 assert(delaySlotInfo != NULL && "No delay slot info for instr?");
838 const SchedGraphNode* delayedNode = S.getChoice(indexForDelayedInstr);
839 MachineOpCode delayOpCode = delayedNode->getMachineInstr()->getOpCode();
840 unsigned ndelays= S.getInstrInfo().getNumDelaySlots(delayOpCode);
842 unsigned delayedNodeSlot = S.nslots;
845 // Find the last possible slot for the delayed instruction that leaves
846 // at least `d' slots vacant after it (d = #delay slots)
847 for (int s = S.nslots-ndelays-1; s >= (int) startSlot; s--)
848 if (S.schedInfo.instrCanUseSlot(delayOpCode, s))
854 highestSlotUsed = -1;
855 for (unsigned i=0; i < S.getNumChoices() - 1; i++)
857 // Try to assign every other instruction to a lower numbered
858 // slot than delayedNodeSlot.
859 MachineOpCode opCode =S.getChoice(i)->getMachineInstr()->getOpCode();
860 bool noSlotFound = true;
862 for (s=startSlot; s < delayedNodeSlot; s++)
863 if (S.schedInfo.instrCanUseSlot(opCode, s))
865 S.addChoiceToSlot(s, S.getChoice(i));
869 // No slot before `delayedNodeSlot' was found for this opCode
870 // Use a later slot, and allow some delay slots to fall in
873 for ( ; s < S.nslots; s++)
874 if (S.schedInfo.instrCanUseSlot(opCode, s))
876 S.addChoiceToSlot(s, S.getChoice(i));
880 assert(s < S.nslots && "No feasible slot for instruction?");
882 highestSlotUsed = max(highestSlotUsed, (int) s);
885 assert(highestSlotUsed <= (int) S.nslots-1 && "Invalid slot used?");
887 // We will put the delayed node in the first slot after the
888 // highest slot used. But we just mark that for now, and
889 // schedule it separately because we want to schedule the delay
890 // slots for the node at the same time.
891 cycles_t dcycle = S.getTime();
892 unsigned int dslot = highestSlotUsed + 1;
893 if (dslot == S.nslots)
898 delaySlotInfo->recordChosenSlot(dcycle, dslot);
899 getDelaySlotInfo = delaySlotInfo;
902 { // There is an instruction that breaks the issue group.
903 // For such an instruction, assign to the last possible slot in
904 // the current group, and then don't assign any other instructions
906 assert(indexForBreakingNode < S.nslots);
907 const SchedGraphNode* breakingNode=S.getChoice(indexForBreakingNode);
908 unsigned breakingSlot = INT_MAX;
909 unsigned int nslotsToUse = S.nslots;
911 // Find the last possible slot for this instruction.
912 for (int s = S.nslots-1; s >= (int) startSlot; s--)
913 if (S.schedInfo.instrCanUseSlot(breakingNode->getMachineInstr()->getOpCode(), s))
918 assert(breakingSlot < S.nslots &&
919 "No feasible slot for `breakingNode'?");
921 // Higher priority instructions than the one that breaks the group:
922 // These can be assigned to all slots, but will be assigned only
923 // to earlier slots if possible.
925 i < S.getNumChoices() && i < indexForBreakingNode; i++)
927 MachineOpCode opCode =S.getChoice(i)->getMachineInstr()->getOpCode();
929 // If a higher priority instruction cannot be assigned to
930 // any earlier slots, don't schedule the breaking instruction.
932 bool foundLowerSlot = false;
933 nslotsToUse = S.nslots; // May be modified in the loop
934 for (unsigned int s=startSlot; s < nslotsToUse; s++)
935 if (S.schedInfo.instrCanUseSlot(opCode, s))
937 if (breakingSlot < S.nslots && s < breakingSlot)
939 foundLowerSlot = true;
940 nslotsToUse = breakingSlot; // RESETS LOOP UPPER BOUND!
943 S.addChoiceToSlot(s, S.getChoice(i));
947 breakingSlot = INT_MAX; // disable breaking instr
950 // Assign the breaking instruction (if any) to a single slot
951 // Otherwise, just ignore the instruction. It will simply be
952 // scheduled in a later cycle.
953 if (breakingSlot < S.nslots)
955 S.addChoiceToSlot(breakingSlot, breakingNode);
956 nslotsToUse = breakingSlot;
959 nslotsToUse = S.nslots;
961 // For lower priority instructions than the one that breaks the
962 // group, only assign them to slots lower than the breaking slot.
963 // Otherwise, just ignore the instruction.
964 for (unsigned i=indexForBreakingNode+1; i < S.getNumChoices(); i++)
966 bool foundLowerSlot = false;
967 MachineOpCode opCode = S.getChoice(i)->getMachineInstr()->getOpCode();
968 for (unsigned int s=startSlot; s < nslotsToUse; s++)
969 if (S.schedInfo.instrCanUseSlot(opCode, s))
970 S.addChoiceToSlot(s, S.getChoice(i));
972 } // endif (no delay slots and no breaking slots)
974 return S.getNumChoices();
979 ChooseOneGroup(SchedulingManager& S)
981 assert(S.schedPrio.getNumReady() > 0
982 && "Don't get here without ready instructions.");
984 cycles_t firstCycle = S.getTime();
985 DelaySlotInfo* getDelaySlotInfo = NULL;
987 // Choose up to `nslots' feasible instructions and their possible slots.
988 unsigned numIssued = FindSlotChoices(S, getDelaySlotInfo);
990 while (numIssued == 0)
992 S.updateTime(S.getTime()+1);
993 numIssued = FindSlotChoices(S, getDelaySlotInfo);
996 AssignInstructionsToSlots(S, numIssued);
998 if (getDelaySlotInfo != NULL)
999 numIssued += getDelaySlotInfo->scheduleDelayedNode(S);
1001 // Print trace of scheduled instructions before newly ready ones
1002 if (SchedDebugLevel >= Sched_PrintSchedTrace)
1004 for (cycles_t c = firstCycle; c <= S.getTime(); c++)
1006 cout << " Cycle " << c << " : Scheduled instructions:\n";
1007 const InstrGroup* igroup = S.isched.getIGroup(c);
1008 for (unsigned int s=0; s < S.nslots; s++)
1011 if ((*igroup)[s] != NULL)
1012 cout << * ((*igroup)[s])->getMachineInstr() << endl;
1014 cout << "<none>" << endl;
1024 ForwardListSchedule(SchedulingManager& S)
1027 const SchedGraphNode* node;
1029 S.schedPrio.initialize();
1031 while ((N = S.schedPrio.getNumReady()) > 0)
1033 cycles_t nextCycle = S.getTime();
1035 // Choose one group of instructions for a cycle, plus any delay slot
1036 // instructions (which may overflow into successive cycles).
1037 // This will advance S.getTime() to the last cycle in which
1038 // instructions are actually issued.
1040 unsigned numIssued = ChooseOneGroup(S);
1041 assert(numIssued > 0 && "Deadlock in list scheduling algorithm?");
1043 // Notify the priority manager of scheduled instructions and mark
1044 // any successors that may now be ready
1046 for (cycles_t c = nextCycle; c <= S.getTime(); c++)
1048 const InstrGroup* igroup = S.isched.getIGroup(c);
1049 for (unsigned int s=0; s < S.nslots; s++)
1050 if ((node = (*igroup)[s]) != NULL)
1052 S.schedPrio.issuedReadyNodeAt(S.getTime(), node);
1053 MarkSuccessorsReady(S, node);
1057 // Move to the next the next earliest cycle for which
1058 // an instruction can be issued, or the next earliest in which
1059 // one will be ready, or to the next cycle, whichever is latest.
1061 S.updateTime(max(S.getTime() + 1,
1062 max(S.getEarliestIssueTime(),
1063 S.schedPrio.getEarliestReadyTime())));
1068 //---------------------------------------------------------------------
1069 // Code for filling delay slots for delayed terminator instructions
1070 // (e.g., BRANCH and RETURN). Delay slots for non-terminator
1071 // instructions (e.g., CALL) are not handled here because they almost
1072 // always can be filled with instructions from the call sequence code
1073 // before a call. That's preferable because we incur many tradeoffs here
1074 // when we cannot find single-cycle instructions that can be reordered.
1075 //----------------------------------------------------------------------
1078 NodeCanFillDelaySlot(const SchedulingManager& S,
1079 const SchedGraphNode* node,
1080 const SchedGraphNode* brNode,
1081 bool nodeIsPredecessor)
1083 assert(! node->isDummyNode());
1085 // don't put a branch in the delay slot of another branch
1086 if (S.getInstrInfo().isBranch(node->getMachineInstr()->getOpCode()))
1089 // don't put a single-issue instruction in the delay slot of a branch
1090 if (S.schedInfo.isSingleIssue(node->getMachineInstr()->getOpCode()))
1093 // don't put a load-use dependence in the delay slot of a branch
1094 const MachineInstrInfo& mii = S.getInstrInfo();
1096 for (SchedGraphNode::const_iterator EI = node->beginInEdges();
1097 EI != node->endInEdges(); ++EI)
1098 if (! (*EI)->getSrc()->isDummyNode()
1099 && mii.isLoad((*EI)->getSrc()->getMachineInstr()->getOpCode())
1100 && (*EI)->getDepType() == SchedGraphEdge::CtrlDep)
1103 // for now, don't put an instruction that does not have operand
1104 // interlocks in the delay slot of a branch
1105 if (! S.getInstrInfo().hasOperandInterlock(node->getMachineInstr()->getOpCode()))
1108 // Finally, if the instruction preceeds the branch, we make sure the
1109 // instruction can be reordered relative to the branch. We simply check
1110 // if the instr. has only 1 outgoing edge, viz., a CD edge to the branch.
1112 if (nodeIsPredecessor)
1114 bool onlyCDEdgeToBranch = true;
1115 for (SchedGraphNode::const_iterator OEI = node->beginOutEdges();
1116 OEI != node->endOutEdges(); ++OEI)
1117 if (! (*OEI)->getSink()->isDummyNode()
1118 && ((*OEI)->getSink() != brNode
1119 || (*OEI)->getDepType() != SchedGraphEdge::CtrlDep))
1121 onlyCDEdgeToBranch = false;
1125 if (!onlyCDEdgeToBranch)
1134 MarkNodeForDelaySlot(SchedulingManager& S,
1136 SchedGraphNode* node,
1137 const SchedGraphNode* brNode,
1138 bool nodeIsPredecessor)
1140 if (nodeIsPredecessor)
1141 { // If node is in the same basic block (i.e., preceeds brNode),
1142 // remove it and all its incident edges from the graph. Make sure we
1143 // add dummy edges for pred/succ nodes that become entry/exit nodes.
1144 graph->eraseIncidentEdges(node, /*addDummyEdges*/ true);
1147 { // If the node was from a target block, add the node to the graph
1148 // and add a CD edge from brNode to node.
1149 assert(0 && "NOT IMPLEMENTED YET");
1152 DelaySlotInfo* dinfo = S.getDelaySlotInfoForInstr(brNode, /*create*/ true);
1153 dinfo->addDelayNode(node);
1158 FindUsefulInstructionsForDelaySlots(SchedulingManager& S,
1159 SchedGraphNode* brNode,
1160 vector<SchedGraphNode*>& sdelayNodeVec)
1162 const MachineInstrInfo& mii = S.getInstrInfo();
1164 mii.getNumDelaySlots(brNode->getMachineInstr()->getOpCode());
1169 sdelayNodeVec.reserve(ndelays);
1171 // Use a separate vector to hold the feasible multi-cycle nodes.
1172 // These will be used if not enough single-cycle nodes are found.
1174 vector<SchedGraphNode*> mdelayNodeVec;
1176 for (sg_pred_iterator P = pred_begin(brNode);
1177 P != pred_end(brNode) && sdelayNodeVec.size() < ndelays; ++P)
1178 if (! (*P)->isDummyNode() &&
1179 ! mii.isNop((*P)->getMachineInstr()->getOpCode()) &&
1180 NodeCanFillDelaySlot(S, *P, brNode, /*pred*/ true))
1182 if (mii.maxLatency((*P)->getMachineInstr()->getOpCode()) > 1)
1183 mdelayNodeVec.push_back(*P);
1185 sdelayNodeVec.push_back(*P);
1188 // If not enough single-cycle instructions were found, select the
1189 // lowest-latency multi-cycle instructions and use them.
1190 // Note that this is the most efficient code when only 1 (or even 2)
1191 // values need to be selected.
1193 while (sdelayNodeVec.size() < ndelays && mdelayNodeVec.size() > 0)
1196 mii.maxLatency(mdelayNodeVec[0]->getMachineInstr()->getOpCode());
1197 unsigned minIndex = 0;
1198 for (unsigned i=1; i < mdelayNodeVec.size(); i++)
1201 mii.maxLatency(mdelayNodeVec[i]->getMachineInstr()->getOpCode());
1208 sdelayNodeVec.push_back(mdelayNodeVec[minIndex]);
1209 if (sdelayNodeVec.size() < ndelays) // avoid the last erase!
1210 mdelayNodeVec.erase(mdelayNodeVec.begin() + minIndex);
1215 // Remove the NOPs currently in delay slots from the graph.
1216 // Mark instructions specified in sdelayNodeVec to replace them.
1217 // If not enough useful instructions were found, mark the NOPs to be used
1218 // for filling delay slots, otherwise, otherwise just discard them.
1221 ReplaceNopsWithUsefulInstr(SchedulingManager& S,
1222 SchedGraphNode* node,
1223 vector<SchedGraphNode*> sdelayNodeVec,
1226 vector<SchedGraphNode*> nopNodeVec; // this will hold unused NOPs
1227 const MachineInstrInfo& mii = S.getInstrInfo();
1228 const MachineInstr* brInstr = node->getMachineInstr();
1229 unsigned ndelays= mii.getNumDelaySlots(brInstr->getOpCode());
1230 assert(ndelays > 0 && "Unnecessary call to replace NOPs");
1232 // Remove the NOPs currently in delay slots from the graph.
1233 // If not enough useful instructions were found, use the NOPs to
1234 // fill delay slots, otherwise, just discard them.
1236 MachineCodeForVMInstr& termMvec = node->getInstr()->getMachineInstrVec();
1237 unsigned int firstDelaySlotIdx;
1238 for (unsigned i=0; i < termMvec.size(); ++i)
1239 if (termMvec[i] == brInstr)
1241 firstDelaySlotIdx = i+1;
1244 assert(firstDelaySlotIdx <= termMvec.size()-1 &&
1245 "This sucks! Where's that delay slot instruction?");
1247 // First find all useful instructions already in the delay slots
1248 // and USE THEM. We'll throw away the unused alternatives below
1250 for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
1251 if (! mii.isNop(termMvec[i]->getOpCode()))
1252 sdelayNodeVec.insert(sdelayNodeVec.begin(),
1253 graph->getGraphNodeForInstr(termMvec[i]));
1255 // Then find the NOPs and keep only as many as are needed.
1256 // Put the rest in nopNodeVec to be deleted.
1257 for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
1258 if (mii.isNop(termMvec[i]->getOpCode()))
1259 if (sdelayNodeVec.size() < ndelays)
1260 sdelayNodeVec.push_back(graph->getGraphNodeForInstr(termMvec[i]));
1262 nopNodeVec.push_back(graph->getGraphNodeForInstr(termMvec[i]));
1264 assert(sdelayNodeVec.size() >= ndelays);
1266 // If some delay slots were already filled, throw away that many new choices
1267 if (sdelayNodeVec.size() > ndelays)
1268 sdelayNodeVec.resize(ndelays);
1270 // Mark the nodes chosen for delay slots. This removes them from the graph.
1271 for (unsigned i=0; i < sdelayNodeVec.size(); i++)
1272 MarkNodeForDelaySlot(S, graph, sdelayNodeVec[i], node, true);
1274 // And remove the unused NOPs from the graph.
1275 for (unsigned i=0; i < nopNodeVec.size(); i++)
1276 graph->eraseIncidentEdges(nopNodeVec[i], /*addDummyEdges*/ true);
1280 // For all delayed instructions, choose instructions to put in the delay
1281 // slots and pull those out of the graph. Mark them for the delay slots
1282 // in the DelaySlotInfo object for that graph node. If no useful work
1283 // is found for a delay slot, use the NOP that is currently in that slot.
1285 // We try to fill the delay slots with useful work for all instructions
1286 // EXCEPT CALLS AND RETURNS.
1287 // For CALLs and RETURNs, it is nearly always possible to use one of the
1288 // call sequence instrs and putting anything else in the delay slot could be
1289 // suboptimal. Also, it complicates generating the calling sequence code in
1293 ChooseInstructionsForDelaySlots(SchedulingManager& S,
1294 const BasicBlock* bb,
1297 const MachineInstrInfo& mii = S.getInstrInfo();
1298 const TerminatorInst* termInstr = bb->getTerminator();
1299 MachineCodeForVMInstr& termMvec = termInstr->getMachineInstrVec();
1300 vector<SchedGraphNode*> delayNodeVec;
1301 const MachineInstr* brInstr = NULL;
1303 assert(termInstr->getOpcode() != Instruction::Call
1304 && "Call used as terminator?");
1306 if (termInstr->getOpcode() != Instruction::Ret)
1308 // To find instructions that need delay slots without searching the full
1309 // machine code, we assume that the only delayed instructions are CALLs
1310 // or instructions generated for the terminator inst.
1311 // Find the first branch instr in the sequence of machine instrs for term
1314 while (first < termMvec.size() &&
1315 ! mii.isBranch(termMvec[first]->getOpCode()))
1319 assert(first < termMvec.size() &&
1320 "No branch instructions for BR? Ok, but weird! Delete assertion.");
1322 brInstr = (first < termMvec.size())? termMvec[first] : NULL;
1324 // Compute a vector of the nodes chosen for delay slots and then
1325 // mark delay slots to replace NOPs with these useful instructions.
1327 if (brInstr != NULL)
1329 SchedGraphNode* brNode = graph->getGraphNodeForInstr(brInstr);
1330 FindUsefulInstructionsForDelaySlots(S, brNode, delayNodeVec);
1331 ReplaceNopsWithUsefulInstr(S, brNode, delayNodeVec, graph);
1335 // Also mark delay slots for other delayed instructions to hold NOPs.
1336 // Simply passing in an empty delayNodeVec will have this effect.
1338 delayNodeVec.clear();
1339 const MachineCodeForBasicBlock& bbMvec = bb->getMachineInstrVec();
1340 for (unsigned i=0; i < bbMvec.size(); i++)
1341 if (bbMvec[i] != brInstr &&
1342 mii.getNumDelaySlots(bbMvec[i]->getOpCode()) > 0)
1344 SchedGraphNode* node = graph->getGraphNodeForInstr(bbMvec[i]);
1345 ReplaceNopsWithUsefulInstr(S, node, delayNodeVec, graph);
1351 // Schedule the delayed branch and its delay slots
1354 DelaySlotInfo::scheduleDelayedNode(SchedulingManager& S)
1356 assert(delayedNodeSlotNum < S.nslots && "Illegal slot for branch");
1357 assert(S.isched.getInstr(delayedNodeSlotNum, delayedNodeCycle) == NULL
1358 && "Slot for branch should be empty");
1360 unsigned int nextSlot = delayedNodeSlotNum;
1361 cycles_t nextTime = delayedNodeCycle;
1363 S.scheduleInstr(brNode, nextSlot, nextTime);
1365 for (unsigned d=0; d < ndelays; d++)
1368 if (nextSlot == S.nslots)
1374 // Find the first feasible instruction for this delay slot
1375 // Note that we only check for issue restrictions here.
1376 // We do *not* check for flow dependences but rely on pipeline
1377 // interlocks to resolve them. Machines without interlocks
1378 // will require this code to be modified.
1379 for (unsigned i=0; i < delayNodeVec.size(); i++)
1381 const SchedGraphNode* dnode = delayNodeVec[i];
1382 if ( ! S.isScheduled(dnode)
1383 && S.schedInfo.instrCanUseSlot(dnode->getMachineInstr()->getOpCode(), nextSlot)
1384 && instrIsFeasible(S, dnode->getMachineInstr()->getOpCode()))
1386 assert(S.getInstrInfo().hasOperandInterlock(dnode->getMachineInstr()->getOpCode())
1387 && "Instructions without interlocks not yet supported "
1388 "when filling branch delay slots");
1389 S.scheduleInstr(dnode, nextSlot, nextTime);
1395 // Update current time if delay slots overflowed into later cycles.
1396 // Do this here because we know exactly which cycle is the last cycle
1397 // that contains delay slots. The next loop doesn't compute that.
1398 if (nextTime > S.getTime())
1399 S.updateTime(nextTime);
1401 // Now put any remaining instructions in the unfilled delay slots.
1402 // This could lead to suboptimal performance but needed for correctness.
1403 nextSlot = delayedNodeSlotNum;
1404 nextTime = delayedNodeCycle;
1405 for (unsigned i=0; i < delayNodeVec.size(); i++)
1406 if (! S.isScheduled(delayNodeVec[i]))
1408 do { // find the next empty slot
1410 if (nextSlot == S.nslots)
1415 } while (S.isched.getInstr(nextSlot, nextTime) != NULL);
1417 S.scheduleInstr(delayNodeVec[i], nextSlot, nextTime);
1425 // Check if the instruction would conflict with instructions already
1426 // chosen for the current cycle
1429 ConflictsWithChoices(const SchedulingManager& S,
1430 MachineOpCode opCode)
1432 // Check if the instruction must issue by itself, and some feasible
1433 // choices have already been made for this cycle
1434 if (S.getNumChoices() > 0 && S.schedInfo.isSingleIssue(opCode))
1437 // For each class that opCode belongs to, check if there are too many
1438 // instructions of that class.
1440 const InstrSchedClass sc = S.schedInfo.getSchedClass(opCode);
1441 return (S.getNumChoicesInClass(sc) == S.schedInfo.getMaxIssueForClass(sc));
1445 //************************* External Functions *****************************/
1448 //---------------------------------------------------------------------------
1449 // Function: ViolatesMinimumGap
1452 // Check minimum gap requirements relative to instructions scheduled in
1454 // Note that we do not need to consider `nextEarliestIssueTime' here because
1455 // that is also captured in the earliest start times for each opcode.
1456 //---------------------------------------------------------------------------
1459 ViolatesMinimumGap(const SchedulingManager& S,
1460 MachineOpCode opCode,
1461 const cycles_t inCycle)
1463 return (inCycle < S.getEarliestStartTimeForOp(opCode));
1467 //---------------------------------------------------------------------------
1468 // Function: instrIsFeasible
1471 // Check if any issue restrictions would prevent the instruction from
1472 // being issued in the current cycle
1473 //---------------------------------------------------------------------------
1476 instrIsFeasible(const SchedulingManager& S,
1477 MachineOpCode opCode)
1479 // skip the instruction if it cannot be issued due to issue restrictions
1480 // caused by previously issued instructions
1481 if (ViolatesMinimumGap(S, opCode, S.getTime()))
1484 // skip the instruction if it cannot be issued due to issue restrictions
1485 // caused by previously chosen instructions for the current cycle
1486 if (ConflictsWithChoices(S, opCode))
1492 //---------------------------------------------------------------------------
1493 // Function: ScheduleInstructionsWithSSA
1496 // Entry point for instruction scheduling on SSA form.
1497 // Schedules the machine instructions generated by instruction selection.
1498 // Assumes that register allocation has not been done, i.e., operands
1499 // are still in SSA form.
1500 //---------------------------------------------------------------------------
1503 ScheduleInstructionsWithSSA(Method* method,
1504 const TargetMachine &target)
1506 SchedGraphSet graphSet(method, target);
1508 if (SchedDebugLevel >= Sched_PrintSchedGraphs)
1510 cout << endl << "*** SCHEDULING GRAPHS FOR INSTRUCTION SCHEDULING"
1515 for (SchedGraphSet::const_iterator GI=graphSet.begin();
1516 GI != graphSet.end(); ++GI)
1518 SchedGraph* graph = (*GI).second;
1519 const vector<const BasicBlock*>& bbvec = graph->getBasicBlocks();
1520 assert(bbvec.size() == 1 && "Cannot schedule multiple basic blocks");
1521 const BasicBlock* bb = bbvec[0];
1523 if (SchedDebugLevel >= Sched_PrintSchedTrace)
1524 cout << endl << "*** TRACE OF INSTRUCTION SCHEDULING OPERATIONS\n\n";
1526 SchedPriorities schedPrio(method, graph); // expensive!
1527 SchedulingManager S(target, graph, schedPrio);
1529 ChooseInstructionsForDelaySlots(S, bb, graph); // modifies graph
1531 ForwardListSchedule(S); // computes schedule in S
1533 RecordSchedule((*GI).first, S); // records schedule in BB
1536 if (SchedDebugLevel >= Sched_PrintMachineCode)
1539 << "*** Machine instructions after INSTRUCTION SCHEDULING" << endl;
1540 MachineCodeForMethod::get(method).dump();
1543 return false; // no reason to fail yet