1 //===- InstrScheduling.cpp - Generic Instruction Scheduling support -------===//
3 // This file implements the llvm/CodeGen/InstrScheduling.h interface, along with
4 // generic support routines for instruction scheduling.
6 //===----------------------------------------------------------------------===//
8 #include "SchedPriorities.h"
9 #include "llvm/CodeGen/MachineInstr.h"
10 #include "llvm/CodeGen/MachineCodeForInstruction.h"
11 #include "llvm/CodeGen/MachineFunction.h"
12 #include "llvm/Analysis/LiveVar/FunctionLiveVarInfo.h" // FIXME: Remove when modularized better
13 #include "llvm/Target/TargetMachine.h"
14 #include "llvm/BasicBlock.h"
15 #include "Support/CommandLine.h"
20 SchedDebugLevel_t SchedDebugLevel;
22 static cl::opt<SchedDebugLevel_t, true>
23 SDL_opt("dsched", cl::Hidden, cl::location(SchedDebugLevel),
24 cl::desc("enable instruction scheduling debugging information"),
26 clEnumValN(Sched_NoDebugInfo, "n", "disable debug output"),
27 clEnumValN(Sched_PrintMachineCode, "y", "print machine code after scheduling"),
28 clEnumValN(Sched_PrintSchedTrace, "t", "print trace of scheduling actions"),
29 clEnumValN(Sched_PrintSchedGraphs, "g", "print scheduling graphs"),
33 //************************* Internal Data Types *****************************/
36 class SchedulingManager;
39 //----------------------------------------------------------------------
42 // Represents a group of instructions scheduled to be issued
44 //----------------------------------------------------------------------
46 class InstrGroup: public NonCopyable {
48 inline const SchedGraphNode* operator[](unsigned int slotNum) const {
49 assert(slotNum < group.size());
50 return group[slotNum];
54 friend class InstrSchedule;
56 inline void addInstr(const SchedGraphNode* node, unsigned int slotNum) {
57 assert(slotNum < group.size());
58 group[slotNum] = node;
61 /*ctor*/ InstrGroup(unsigned int nslots)
62 : group(nslots, NULL) {}
64 /*ctor*/ InstrGroup(); // disable: DO NOT IMPLEMENT
67 vector<const SchedGraphNode*> group;
71 //----------------------------------------------------------------------
72 // class ScheduleIterator:
74 // Iterates over the machine instructions in the for a single basic block.
75 // The schedule is represented by an InstrSchedule object.
76 //----------------------------------------------------------------------
78 template<class _NodeType>
79 class ScheduleIterator : public forward_iterator<_NodeType, ptrdiff_t> {
83 const InstrSchedule& S;
85 typedef ScheduleIterator<_NodeType> _Self;
87 /*ctor*/ inline ScheduleIterator(const InstrSchedule& _schedule,
90 : cycleNum(_cycleNum), slotNum(_slotNum), S(_schedule) {
94 /*ctor*/ inline ScheduleIterator(const _Self& x)
95 : cycleNum(x.cycleNum), slotNum(x.slotNum), S(x.S) {}
97 inline bool operator==(const _Self& x) const {
98 return (slotNum == x.slotNum && cycleNum== x.cycleNum && &S==&x.S);
101 inline bool operator!=(const _Self& x) const { return !operator==(x); }
103 inline _NodeType* operator*() const {
104 assert(cycleNum < S.groups.size());
105 return (*S.groups[cycleNum])[slotNum];
107 inline _NodeType* operator->() const { return operator*(); }
109 _Self& operator++(); // Preincrement
110 inline _Self operator++(int) { // Postincrement
111 _Self tmp(*this); ++*this; return tmp;
114 static _Self begin(const InstrSchedule& _schedule);
115 static _Self end( const InstrSchedule& _schedule);
118 inline _Self& operator=(const _Self& x); // DISABLE -- DO NOT IMPLEMENT
119 void skipToNextInstr();
123 //----------------------------------------------------------------------
124 // class InstrSchedule:
126 // Represents the schedule of machine instructions for a single basic block.
127 //----------------------------------------------------------------------
129 class InstrSchedule: public NonCopyable {
131 const unsigned int nslots;
132 unsigned int numInstr;
133 vector<InstrGroup*> groups; // indexed by cycle number
134 vector<cycles_t> startTime; // indexed by node id
137 typedef ScheduleIterator<SchedGraphNode> iterator;
138 typedef ScheduleIterator<const SchedGraphNode> const_iterator;
141 const_iterator begin() const;
143 const_iterator end() const;
145 public: // constructors and destructor
146 /*ctor*/ InstrSchedule (unsigned int _nslots,
147 unsigned int _numNodes);
148 /*dtor*/ ~InstrSchedule ();
150 public: // accessor functions to query chosen schedule
151 const SchedGraphNode* getInstr (unsigned int slotNum,
153 const InstrGroup* igroup = this->getIGroup(c);
154 return (igroup == NULL)? NULL : (*igroup)[slotNum];
157 inline InstrGroup* getIGroup (cycles_t c) {
158 if ((unsigned)c >= groups.size())
160 if (groups[c] == NULL)
161 groups[c] = new InstrGroup(nslots);
165 inline const InstrGroup* getIGroup (cycles_t c) const {
166 assert((unsigned)c < groups.size());
170 inline cycles_t getStartTime (unsigned int nodeId) const {
171 assert(nodeId < startTime.size());
172 return startTime[nodeId];
175 unsigned int getNumInstructions() const {
179 inline void scheduleInstr (const SchedGraphNode* node,
180 unsigned int slotNum,
182 InstrGroup* igroup = this->getIGroup(cycle);
183 assert((*igroup)[slotNum] == NULL && "Slot already filled?");
184 igroup->addInstr(node, slotNum);
185 assert(node->getNodeId() < startTime.size());
186 startTime[node->getNodeId()] = cycle;
191 friend class iterator;
192 friend class const_iterator;
193 /*ctor*/ InstrSchedule (); // Disable: DO NOT IMPLEMENT.
198 InstrSchedule::InstrSchedule(unsigned int _nslots, unsigned int _numNodes)
201 groups(2 * _numNodes / _nslots), // 2 x lower-bound for #cycles
202 startTime(_numNodes, (cycles_t) -1) // set all to -1
208 InstrSchedule::~InstrSchedule()
210 for (unsigned c=0, NC=groups.size(); c < NC; c++)
211 if (groups[c] != NULL)
212 delete groups[c]; // delete InstrGroup objects
216 template<class _NodeType>
219 ScheduleIterator<_NodeType>::skipToNextInstr()
221 while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
222 ++cycleNum; // skip cycles with no instructions
224 while (cycleNum < S.groups.size() &&
225 (*S.groups[cycleNum])[slotNum] == NULL)
228 if (slotNum == S.nslots)
232 while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
233 ++cycleNum; // skip cycles with no instructions
238 template<class _NodeType>
240 ScheduleIterator<_NodeType>&
241 ScheduleIterator<_NodeType>::operator++() // Preincrement
244 if (slotNum == S.nslots)
253 template<class _NodeType>
254 ScheduleIterator<_NodeType>
255 ScheduleIterator<_NodeType>::begin(const InstrSchedule& _schedule)
257 return _Self(_schedule, 0, 0);
260 template<class _NodeType>
261 ScheduleIterator<_NodeType>
262 ScheduleIterator<_NodeType>::end(const InstrSchedule& _schedule)
264 return _Self(_schedule, _schedule.groups.size(), 0);
267 InstrSchedule::iterator
268 InstrSchedule::begin()
270 return iterator::begin(*this);
273 InstrSchedule::const_iterator
274 InstrSchedule::begin() const
276 return const_iterator::begin(*this);
279 InstrSchedule::iterator
282 return iterator::end(*this);
285 InstrSchedule::const_iterator
286 InstrSchedule::end() const
288 return const_iterator::end( *this);
292 //----------------------------------------------------------------------
293 // class DelaySlotInfo:
295 // Record information about delay slots for a single branch instruction.
296 // Delay slots are simply indexed by slot number 1 ... numDelaySlots
297 //----------------------------------------------------------------------
299 class DelaySlotInfo: public NonCopyable {
301 const SchedGraphNode* brNode;
302 unsigned int ndelays;
303 vector<const SchedGraphNode*> delayNodeVec;
304 cycles_t delayedNodeCycle;
305 unsigned int delayedNodeSlotNum;
308 /*ctor*/ DelaySlotInfo (const SchedGraphNode* _brNode,
310 : brNode(_brNode), ndelays(_ndelays),
311 delayedNodeCycle(0), delayedNodeSlotNum(0) {}
313 inline unsigned getNumDelays () {
317 inline const vector<const SchedGraphNode*>& getDelayNodeVec() {
321 inline void addDelayNode (const SchedGraphNode* node) {
322 delayNodeVec.push_back(node);
323 assert(delayNodeVec.size() <= ndelays && "Too many delay slot instrs!");
326 inline void recordChosenSlot (cycles_t cycle, unsigned slotNum) {
327 delayedNodeCycle = cycle;
328 delayedNodeSlotNum = slotNum;
331 unsigned scheduleDelayedNode (SchedulingManager& S);
335 //----------------------------------------------------------------------
336 // class SchedulingManager:
338 // Represents the schedule of machine instructions for a single basic block.
339 //----------------------------------------------------------------------
341 class SchedulingManager: public NonCopyable {
342 public: // publicly accessible data members
343 const unsigned nslots;
344 const TargetSchedInfo& schedInfo;
345 SchedPriorities& schedPrio;
346 InstrSchedule isched;
349 unsigned int totalInstrCount;
351 cycles_t nextEarliestIssueTime; // next cycle we can issue
352 vector<hash_set<const SchedGraphNode*> > choicesForSlot; // indexed by slot#
353 vector<const SchedGraphNode*> choiceVec; // indexed by node ptr
354 vector<int> numInClass; // indexed by sched class
355 vector<cycles_t> nextEarliestStartTime; // indexed by opCode
356 hash_map<const SchedGraphNode*, DelaySlotInfo*> delaySlotInfoForBranches;
357 // indexed by branch node ptr
360 SchedulingManager(const TargetMachine& _target, const SchedGraph* graph,
361 SchedPriorities& schedPrio);
362 ~SchedulingManager() {
363 for (hash_map<const SchedGraphNode*,
364 DelaySlotInfo*>::iterator I = delaySlotInfoForBranches.begin(),
365 E = delaySlotInfoForBranches.end(); I != E; ++I)
369 //----------------------------------------------------------------------
370 // Simplify access to the machine instruction info
371 //----------------------------------------------------------------------
373 inline const TargetInstrInfo& getInstrInfo () const {
374 return schedInfo.getInstrInfo();
377 //----------------------------------------------------------------------
378 // Interface for checking and updating the current time
379 //----------------------------------------------------------------------
381 inline cycles_t getTime () const {
385 inline cycles_t getEarliestIssueTime() const {
386 return nextEarliestIssueTime;
389 inline cycles_t getEarliestStartTimeForOp(MachineOpCode opCode) const {
390 assert(opCode < (int) nextEarliestStartTime.size());
391 return nextEarliestStartTime[opCode];
394 // Update current time to specified cycle
395 inline void updateTime (cycles_t c) {
397 schedPrio.updateTime(c);
400 //----------------------------------------------------------------------
401 // Functions to manage the choices for the current cycle including:
402 // -- a vector of choices by priority (choiceVec)
403 // -- vectors of the choices for each instruction slot (choicesForSlot[])
404 // -- number of choices in each sched class, used to check issue conflicts
405 // between choices for a single cycle
406 //----------------------------------------------------------------------
408 inline unsigned int getNumChoices () const {
409 return choiceVec.size();
412 inline unsigned getNumChoicesInClass (const InstrSchedClass& sc) const {
413 assert(sc < numInClass.size() && "Invalid op code or sched class!");
414 return numInClass[sc];
417 inline const SchedGraphNode* getChoice(unsigned int i) const {
418 // assert(i < choiceVec.size()); don't check here.
422 inline hash_set<const SchedGraphNode*>& getChoicesForSlot(unsigned slotNum) {
423 assert(slotNum < nslots);
424 return choicesForSlot[slotNum];
427 inline void addChoice (const SchedGraphNode* node) {
428 // Append the instruction to the vector of choices for current cycle.
429 // Increment numInClass[c] for the sched class to which the instr belongs.
430 choiceVec.push_back(node);
431 const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpCode());
432 assert(sc < numInClass.size());
436 inline void addChoiceToSlot (unsigned int slotNum,
437 const SchedGraphNode* node) {
438 // Add the instruction to the choice set for the specified slot
439 assert(slotNum < nslots);
440 choicesForSlot[slotNum].insert(node);
443 inline void resetChoices () {
445 for (unsigned int s=0; s < nslots; s++)
446 choicesForSlot[s].clear();
447 for (unsigned int c=0; c < numInClass.size(); c++)
451 //----------------------------------------------------------------------
452 // Code to query and manage the partial instruction schedule so far
453 //----------------------------------------------------------------------
455 inline unsigned int getNumScheduled () const {
456 return isched.getNumInstructions();
459 inline unsigned int getNumUnscheduled() const {
460 return totalInstrCount - isched.getNumInstructions();
463 inline bool isScheduled (const SchedGraphNode* node) const {
464 return (isched.getStartTime(node->getNodeId()) >= 0);
467 inline void scheduleInstr (const SchedGraphNode* node,
468 unsigned int slotNum,
471 assert(! isScheduled(node) && "Instruction already scheduled?");
473 // add the instruction to the schedule
474 isched.scheduleInstr(node, slotNum, cycle);
476 // update the earliest start times of all nodes that conflict with `node'
477 // and the next-earliest time anything can issue if `node' causes bubbles
478 updateEarliestStartTimes(node, cycle);
480 // remove the instruction from the choice sets for all slots
481 for (unsigned s=0; s < nslots; s++)
482 choicesForSlot[s].erase(node);
484 // and decrement the instr count for the sched class to which it belongs
485 const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpCode());
486 assert(sc < numInClass.size());
490 //----------------------------------------------------------------------
491 // Create and retrieve delay slot info for delayed instructions
492 //----------------------------------------------------------------------
494 inline DelaySlotInfo* getDelaySlotInfoForInstr(const SchedGraphNode* bn,
495 bool createIfMissing=false)
497 hash_map<const SchedGraphNode*, DelaySlotInfo*>::const_iterator
498 I = delaySlotInfoForBranches.find(bn);
499 if (I != delaySlotInfoForBranches.end())
502 if (!createIfMissing) return 0;
504 DelaySlotInfo *dinfo =
505 new DelaySlotInfo(bn, getInstrInfo().getNumDelaySlots(bn->getOpCode()));
506 return delaySlotInfoForBranches[bn] = dinfo;
510 SchedulingManager(); // DISABLED: DO NOT IMPLEMENT
511 void updateEarliestStartTimes(const SchedGraphNode* node, cycles_t schedTime);
516 SchedulingManager::SchedulingManager(const TargetMachine& target,
517 const SchedGraph* graph,
518 SchedPriorities& _schedPrio)
519 : nslots(target.getSchedInfo().getMaxNumIssueTotal()),
520 schedInfo(target.getSchedInfo()),
521 schedPrio(_schedPrio),
522 isched(nslots, graph->getNumNodes()),
523 totalInstrCount(graph->getNumNodes() - 2),
524 nextEarliestIssueTime(0),
525 choicesForSlot(nslots),
526 numInClass(target.getSchedInfo().getNumSchedClasses(), 0), // set all to 0
527 nextEarliestStartTime(target.getInstrInfo().getNumRealOpCodes(),
528 (cycles_t) 0) // set all to 0
532 // Note that an upper bound on #choices for each slot is = nslots since
533 // we use this vector to hold a feasible set of instructions, and more
534 // would be infeasible. Reserve that much memory since it is probably small.
535 for (unsigned int i=0; i < nslots; i++)
536 choicesForSlot[i].resize(nslots);
541 SchedulingManager::updateEarliestStartTimes(const SchedGraphNode* node,
544 if (schedInfo.numBubblesAfter(node->getOpCode()) > 0)
545 { // Update next earliest time before which *nothing* can issue.
546 nextEarliestIssueTime = std::max(nextEarliestIssueTime,
547 curTime + 1 + schedInfo.numBubblesAfter(node->getOpCode()));
550 const std::vector<MachineOpCode>&
551 conflictVec = schedInfo.getConflictList(node->getOpCode());
553 for (unsigned i=0; i < conflictVec.size(); i++)
555 MachineOpCode toOp = conflictVec[i];
556 cycles_t est=schedTime + schedInfo.getMinIssueGap(node->getOpCode(),toOp);
557 assert(toOp < (int) nextEarliestStartTime.size());
558 if (nextEarliestStartTime[toOp] < est)
559 nextEarliestStartTime[toOp] = est;
563 //************************* Internal Functions *****************************/
567 AssignInstructionsToSlots(class SchedulingManager& S, unsigned maxIssue)
569 // find the slot to start from, in the current cycle
570 unsigned int startSlot = 0;
571 cycles_t curTime = S.getTime();
573 assert(maxIssue > 0 && maxIssue <= S.nslots - startSlot);
575 // If only one instruction can be issued, do so.
577 for (unsigned s=startSlot; s < S.nslots; s++)
578 if (S.getChoicesForSlot(s).size() > 0)
579 {// found the one instruction
580 S.scheduleInstr(*S.getChoicesForSlot(s).begin(), s, curTime);
584 // Otherwise, choose from the choices for each slot
586 InstrGroup* igroup = S.isched.getIGroup(S.getTime());
587 assert(igroup != NULL && "Group creation failed?");
589 // Find a slot that has only a single choice, and take it.
590 // If all slots have 0 or multiple choices, pick the first slot with
591 // choices and use its last instruction (just to avoid shifting the vector).
593 for (numIssued = 0; numIssued < maxIssue; numIssued++)
596 for (unsigned s=startSlot; s < S.nslots; s++)
597 if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() == 1)
599 chosenSlot = (int) s;
603 if (chosenSlot == -1)
604 for (unsigned s=startSlot; s < S.nslots; s++)
605 if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() > 0)
607 chosenSlot = (int) s;
611 if (chosenSlot != -1)
612 { // Insert the chosen instr in the chosen slot and
613 // erase it from all slots.
614 const SchedGraphNode* node= *S.getChoicesForSlot(chosenSlot).begin();
615 S.scheduleInstr(node, chosenSlot, curTime);
619 assert(numIssued > 0 && "Should not happen when maxIssue > 0!");
624 // For now, just assume we are scheduling within a single basic block.
625 // Get the machine instruction vector for the basic block and clear it,
626 // then append instructions in scheduled order.
627 // Also, re-insert the dummy PHI instructions that were at the beginning
628 // of the basic block, since they are not part of the schedule.
631 RecordSchedule(MachineBasicBlock &MBB, const SchedulingManager& S)
633 const TargetInstrInfo& mii = S.schedInfo.getInstrInfo();
636 // Lets make sure we didn't lose any instructions, except possibly
637 // some NOPs from delay slots. Also, PHIs are not included in the schedule.
638 unsigned numInstr = 0;
639 for (MachineBasicBlock::iterator I=MBB.begin(); I != MBB.end(); ++I)
640 if (! mii.isNop((*I)->getOpCode()) &&
641 ! mii.isDummyPhiInstr((*I)->getOpCode()))
643 assert(S.isched.getNumInstructions() >= numInstr &&
644 "Lost some non-NOP instructions during scheduling!");
647 if (S.isched.getNumInstructions() == 0)
648 return; // empty basic block!
650 // First find the dummy instructions at the start of the basic block
651 MachineBasicBlock::iterator I = MBB.begin();
652 for ( ; I != MBB.end(); ++I)
653 if (! mii.isDummyPhiInstr((*I)->getOpCode()))
656 // Erase all except the dummy PHI instructions from MBB, and
657 // pre-allocate create space for the ones we will put back in.
658 MBB.erase(I, MBB.end());
660 InstrSchedule::const_iterator NIend = S.isched.end();
661 for (InstrSchedule::const_iterator NI = S.isched.begin(); NI != NIend; ++NI)
662 MBB.push_back(const_cast<MachineInstr*>((*NI)->getMachineInstr()));
668 MarkSuccessorsReady(SchedulingManager& S, const SchedGraphNode* node)
670 // Check if any successors are now ready that were not already marked
671 // ready before, and that have not yet been scheduled.
673 for (sg_succ_const_iterator SI = succ_begin(node); SI !=succ_end(node); ++SI)
674 if (! (*SI)->isDummyNode()
675 && ! S.isScheduled(*SI)
676 && ! S.schedPrio.nodeIsReady(*SI))
677 {// successor not scheduled and not marked ready; check *its* preds.
679 bool succIsReady = true;
680 for (sg_pred_const_iterator P=pred_begin(*SI); P != pred_end(*SI); ++P)
681 if (! (*P)->isDummyNode()
682 && ! S.isScheduled(*P))
688 if (succIsReady) // add the successor to the ready list
689 S.schedPrio.insertReady(*SI);
694 // Choose up to `nslots' FEASIBLE instructions and assign each
695 // instruction to all possible slots that do not violate feasibility.
696 // FEASIBLE means it should be guaranteed that the set
697 // of chosen instructions can be issued in a single group.
700 // maxIssue : total number of feasible instructions
701 // S.choicesForSlot[i=0..nslots] : set of instructions feasible in slot i
704 FindSlotChoices(SchedulingManager& S,
705 DelaySlotInfo*& getDelaySlotInfo)
707 // initialize result vectors to empty
710 // find the slot to start from, in the current cycle
711 unsigned int startSlot = 0;
712 InstrGroup* igroup = S.isched.getIGroup(S.getTime());
713 for (int s = S.nslots - 1; s >= 0; s--)
714 if ((*igroup)[s] != NULL)
720 // Make sure we pick at most one instruction that would break the group.
721 // Also, if we do pick one, remember which it was.
722 unsigned int indexForBreakingNode = S.nslots;
723 unsigned int indexForDelayedInstr = S.nslots;
724 DelaySlotInfo* delaySlotInfo = NULL;
726 getDelaySlotInfo = NULL;
728 // Choose instructions in order of priority.
729 // Add choices to the choice vector in the SchedulingManager class as
730 // we choose them so that subsequent choices will be correctly tested
731 // for feasibility, w.r.t. higher priority choices for the same cycle.
733 while (S.getNumChoices() < S.nslots - startSlot)
735 const SchedGraphNode* nextNode=S.schedPrio.getNextHighest(S,S.getTime());
736 if (nextNode == NULL)
737 break; // no more instructions for this cycle
739 if (S.getInstrInfo().getNumDelaySlots(nextNode->getOpCode()) > 0)
741 delaySlotInfo = S.getDelaySlotInfoForInstr(nextNode);
742 if (delaySlotInfo != NULL)
744 if (indexForBreakingNode < S.nslots)
745 // cannot issue a delayed instr in the same cycle as one
746 // that breaks the issue group or as another delayed instr
749 indexForDelayedInstr = S.getNumChoices();
752 else if (S.schedInfo.breaksIssueGroup(nextNode->getOpCode()))
754 if (indexForBreakingNode < S.nslots)
755 // have a breaking instruction already so throw this one away
758 indexForBreakingNode = S.getNumChoices();
761 if (nextNode != NULL)
763 S.addChoice(nextNode);
765 if (S.schedInfo.isSingleIssue(nextNode->getOpCode()))
767 assert(S.getNumChoices() == 1 &&
768 "Prioritizer returned invalid instr for this cycle!");
773 if (indexForDelayedInstr < S.nslots)
774 break; // leave the rest for delay slots
777 assert(S.getNumChoices() <= S.nslots);
778 assert(! (indexForDelayedInstr < S.nslots &&
779 indexForBreakingNode < S.nslots) && "Cannot have both in a cycle");
781 // Assign each chosen instruction to all possible slots for that instr.
782 // But if only one instruction was chosen, put it only in the first
783 // feasible slot; no more analysis will be needed.
785 if (indexForDelayedInstr >= S.nslots &&
786 indexForBreakingNode >= S.nslots)
787 { // No instructions that break the issue group or that have delay slots.
788 // This is the common case, so handle it separately for efficiency.
790 if (S.getNumChoices() == 1)
792 MachineOpCode opCode = S.getChoice(0)->getOpCode();
794 for (s=startSlot; s < S.nslots; s++)
795 if (S.schedInfo.instrCanUseSlot(opCode, s))
797 assert(s < S.nslots && "No feasible slot for this opCode?");
798 S.addChoiceToSlot(s, S.getChoice(0));
802 for (unsigned i=0; i < S.getNumChoices(); i++)
804 MachineOpCode opCode = S.getChoice(i)->getOpCode();
805 for (unsigned int s=startSlot; s < S.nslots; s++)
806 if (S.schedInfo.instrCanUseSlot(opCode, s))
807 S.addChoiceToSlot(s, S.getChoice(i));
811 else if (indexForDelayedInstr < S.nslots)
813 // There is an instruction that needs delay slots.
814 // Try to assign that instruction to a higher slot than any other
815 // instructions in the group, so that its delay slots can go
819 assert(indexForDelayedInstr == S.getNumChoices() - 1 &&
820 "Instruction with delay slots should be last choice!");
821 assert(delaySlotInfo != NULL && "No delay slot info for instr?");
823 const SchedGraphNode* delayedNode = S.getChoice(indexForDelayedInstr);
824 MachineOpCode delayOpCode = delayedNode->getOpCode();
825 unsigned ndelays= S.getInstrInfo().getNumDelaySlots(delayOpCode);
827 unsigned delayedNodeSlot = S.nslots;
830 // Find the last possible slot for the delayed instruction that leaves
831 // at least `d' slots vacant after it (d = #delay slots)
832 for (int s = S.nslots-ndelays-1; s >= (int) startSlot; s--)
833 if (S.schedInfo.instrCanUseSlot(delayOpCode, s))
839 highestSlotUsed = -1;
840 for (unsigned i=0; i < S.getNumChoices() - 1; i++)
842 // Try to assign every other instruction to a lower numbered
843 // slot than delayedNodeSlot.
844 MachineOpCode opCode =S.getChoice(i)->getOpCode();
845 bool noSlotFound = true;
847 for (s=startSlot; s < delayedNodeSlot; s++)
848 if (S.schedInfo.instrCanUseSlot(opCode, s))
850 S.addChoiceToSlot(s, S.getChoice(i));
854 // No slot before `delayedNodeSlot' was found for this opCode
855 // Use a later slot, and allow some delay slots to fall in
858 for ( ; s < S.nslots; s++)
859 if (S.schedInfo.instrCanUseSlot(opCode, s))
861 S.addChoiceToSlot(s, S.getChoice(i));
865 assert(s < S.nslots && "No feasible slot for instruction?");
867 highestSlotUsed = std::max(highestSlotUsed, (int) s);
870 assert(highestSlotUsed <= (int) S.nslots-1 && "Invalid slot used?");
872 // We will put the delayed node in the first slot after the
873 // highest slot used. But we just mark that for now, and
874 // schedule it separately because we want to schedule the delay
875 // slots for the node at the same time.
876 cycles_t dcycle = S.getTime();
877 unsigned int dslot = highestSlotUsed + 1;
878 if (dslot == S.nslots)
883 delaySlotInfo->recordChosenSlot(dcycle, dslot);
884 getDelaySlotInfo = delaySlotInfo;
887 { // There is an instruction that breaks the issue group.
888 // For such an instruction, assign to the last possible slot in
889 // the current group, and then don't assign any other instructions
891 assert(indexForBreakingNode < S.nslots);
892 const SchedGraphNode* breakingNode=S.getChoice(indexForBreakingNode);
893 unsigned breakingSlot = INT_MAX;
894 unsigned int nslotsToUse = S.nslots;
896 // Find the last possible slot for this instruction.
897 for (int s = S.nslots-1; s >= (int) startSlot; s--)
898 if (S.schedInfo.instrCanUseSlot(breakingNode->getOpCode(), s))
903 assert(breakingSlot < S.nslots &&
904 "No feasible slot for `breakingNode'?");
906 // Higher priority instructions than the one that breaks the group:
907 // These can be assigned to all slots, but will be assigned only
908 // to earlier slots if possible.
910 i < S.getNumChoices() && i < indexForBreakingNode; i++)
912 MachineOpCode opCode =S.getChoice(i)->getOpCode();
914 // If a higher priority instruction cannot be assigned to
915 // any earlier slots, don't schedule the breaking instruction.
917 bool foundLowerSlot = false;
918 nslotsToUse = S.nslots; // May be modified in the loop
919 for (unsigned int s=startSlot; s < nslotsToUse; s++)
920 if (S.schedInfo.instrCanUseSlot(opCode, s))
922 if (breakingSlot < S.nslots && s < breakingSlot)
924 foundLowerSlot = true;
925 nslotsToUse = breakingSlot; // RESETS LOOP UPPER BOUND!
928 S.addChoiceToSlot(s, S.getChoice(i));
932 breakingSlot = INT_MAX; // disable breaking instr
935 // Assign the breaking instruction (if any) to a single slot
936 // Otherwise, just ignore the instruction. It will simply be
937 // scheduled in a later cycle.
938 if (breakingSlot < S.nslots)
940 S.addChoiceToSlot(breakingSlot, breakingNode);
941 nslotsToUse = breakingSlot;
944 nslotsToUse = S.nslots;
946 // For lower priority instructions than the one that breaks the
947 // group, only assign them to slots lower than the breaking slot.
948 // Otherwise, just ignore the instruction.
949 for (unsigned i=indexForBreakingNode+1; i < S.getNumChoices(); i++)
951 MachineOpCode opCode = S.getChoice(i)->getOpCode();
952 for (unsigned int s=startSlot; s < nslotsToUse; s++)
953 if (S.schedInfo.instrCanUseSlot(opCode, s))
954 S.addChoiceToSlot(s, S.getChoice(i));
956 } // endif (no delay slots and no breaking slots)
958 return S.getNumChoices();
963 ChooseOneGroup(SchedulingManager& S)
965 assert(S.schedPrio.getNumReady() > 0
966 && "Don't get here without ready instructions.");
968 cycles_t firstCycle = S.getTime();
969 DelaySlotInfo* getDelaySlotInfo = NULL;
971 // Choose up to `nslots' feasible instructions and their possible slots.
972 unsigned numIssued = FindSlotChoices(S, getDelaySlotInfo);
974 while (numIssued == 0)
976 S.updateTime(S.getTime()+1);
977 numIssued = FindSlotChoices(S, getDelaySlotInfo);
980 AssignInstructionsToSlots(S, numIssued);
982 if (getDelaySlotInfo != NULL)
983 numIssued += getDelaySlotInfo->scheduleDelayedNode(S);
985 // Print trace of scheduled instructions before newly ready ones
986 if (SchedDebugLevel >= Sched_PrintSchedTrace)
988 for (cycles_t c = firstCycle; c <= S.getTime(); c++)
990 cerr << " Cycle " << (long)c << " : Scheduled instructions:\n";
991 const InstrGroup* igroup = S.isched.getIGroup(c);
992 for (unsigned int s=0; s < S.nslots; s++)
995 if ((*igroup)[s] != NULL)
996 cerr << * ((*igroup)[s])->getMachineInstr() << "\n";
1008 ForwardListSchedule(SchedulingManager& S)
1011 const SchedGraphNode* node;
1013 S.schedPrio.initialize();
1015 while ((N = S.schedPrio.getNumReady()) > 0)
1017 cycles_t nextCycle = S.getTime();
1019 // Choose one group of instructions for a cycle, plus any delay slot
1020 // instructions (which may overflow into successive cycles).
1021 // This will advance S.getTime() to the last cycle in which
1022 // instructions are actually issued.
1024 unsigned numIssued = ChooseOneGroup(S);
1025 assert(numIssued > 0 && "Deadlock in list scheduling algorithm?");
1027 // Notify the priority manager of scheduled instructions and mark
1028 // any successors that may now be ready
1030 for (cycles_t c = nextCycle; c <= S.getTime(); c++)
1032 const InstrGroup* igroup = S.isched.getIGroup(c);
1033 for (unsigned int s=0; s < S.nslots; s++)
1034 if ((node = (*igroup)[s]) != NULL)
1036 S.schedPrio.issuedReadyNodeAt(S.getTime(), node);
1037 MarkSuccessorsReady(S, node);
1041 // Move to the next the next earliest cycle for which
1042 // an instruction can be issued, or the next earliest in which
1043 // one will be ready, or to the next cycle, whichever is latest.
1045 S.updateTime(std::max(S.getTime() + 1,
1046 std::max(S.getEarliestIssueTime(),
1047 S.schedPrio.getEarliestReadyTime())));
1052 //---------------------------------------------------------------------
1053 // Code for filling delay slots for delayed terminator instructions
1054 // (e.g., BRANCH and RETURN). Delay slots for non-terminator
1055 // instructions (e.g., CALL) are not handled here because they almost
1056 // always can be filled with instructions from the call sequence code
1057 // before a call. That's preferable because we incur many tradeoffs here
1058 // when we cannot find single-cycle instructions that can be reordered.
1059 //----------------------------------------------------------------------
1062 NodeCanFillDelaySlot(const SchedulingManager& S,
1063 const SchedGraphNode* node,
1064 const SchedGraphNode* brNode,
1065 bool nodeIsPredecessor)
1067 assert(! node->isDummyNode());
1069 // don't put a branch in the delay slot of another branch
1070 if (S.getInstrInfo().isBranch(node->getOpCode()))
1073 // don't put a single-issue instruction in the delay slot of a branch
1074 if (S.schedInfo.isSingleIssue(node->getOpCode()))
1077 // don't put a load-use dependence in the delay slot of a branch
1078 const TargetInstrInfo& mii = S.getInstrInfo();
1080 for (SchedGraphNode::const_iterator EI = node->beginInEdges();
1081 EI != node->endInEdges(); ++EI)
1082 if (! (*EI)->getSrc()->isDummyNode()
1083 && mii.isLoad((*EI)->getSrc()->getOpCode())
1084 && (*EI)->getDepType() == SchedGraphEdge::CtrlDep)
1087 // for now, don't put an instruction that does not have operand
1088 // interlocks in the delay slot of a branch
1089 if (! S.getInstrInfo().hasOperandInterlock(node->getOpCode()))
1092 // Finally, if the instruction preceeds the branch, we make sure the
1093 // instruction can be reordered relative to the branch. We simply check
1094 // if the instr. has only 1 outgoing edge, viz., a CD edge to the branch.
1096 if (nodeIsPredecessor)
1098 bool onlyCDEdgeToBranch = true;
1099 for (SchedGraphNode::const_iterator OEI = node->beginOutEdges();
1100 OEI != node->endOutEdges(); ++OEI)
1101 if (! (*OEI)->getSink()->isDummyNode()
1102 && ((*OEI)->getSink() != brNode
1103 || (*OEI)->getDepType() != SchedGraphEdge::CtrlDep))
1105 onlyCDEdgeToBranch = false;
1109 if (!onlyCDEdgeToBranch)
1118 MarkNodeForDelaySlot(SchedulingManager& S,
1120 SchedGraphNode* node,
1121 const SchedGraphNode* brNode,
1122 bool nodeIsPredecessor)
1124 if (nodeIsPredecessor)
1125 { // If node is in the same basic block (i.e., preceeds brNode),
1126 // remove it and all its incident edges from the graph. Make sure we
1127 // add dummy edges for pred/succ nodes that become entry/exit nodes.
1128 graph->eraseIncidentEdges(node, /*addDummyEdges*/ true);
1131 { // If the node was from a target block, add the node to the graph
1132 // and add a CD edge from brNode to node.
1133 assert(0 && "NOT IMPLEMENTED YET");
1136 DelaySlotInfo* dinfo = S.getDelaySlotInfoForInstr(brNode, /*create*/ true);
1137 dinfo->addDelayNode(node);
1142 FindUsefulInstructionsForDelaySlots(SchedulingManager& S,
1143 SchedGraphNode* brNode,
1144 vector<SchedGraphNode*>& sdelayNodeVec)
1146 const TargetInstrInfo& mii = S.getInstrInfo();
1148 mii.getNumDelaySlots(brNode->getOpCode());
1153 sdelayNodeVec.reserve(ndelays);
1155 // Use a separate vector to hold the feasible multi-cycle nodes.
1156 // These will be used if not enough single-cycle nodes are found.
1158 vector<SchedGraphNode*> mdelayNodeVec;
1160 for (sg_pred_iterator P = pred_begin(brNode);
1161 P != pred_end(brNode) && sdelayNodeVec.size() < ndelays; ++P)
1162 if (! (*P)->isDummyNode() &&
1163 ! mii.isNop((*P)->getOpCode()) &&
1164 NodeCanFillDelaySlot(S, *P, brNode, /*pred*/ true))
1166 if (mii.maxLatency((*P)->getOpCode()) > 1)
1167 mdelayNodeVec.push_back(*P);
1169 sdelayNodeVec.push_back(*P);
1172 // If not enough single-cycle instructions were found, select the
1173 // lowest-latency multi-cycle instructions and use them.
1174 // Note that this is the most efficient code when only 1 (or even 2)
1175 // values need to be selected.
1177 while (sdelayNodeVec.size() < ndelays && mdelayNodeVec.size() > 0)
1180 mii.maxLatency(mdelayNodeVec[0]->getOpCode());
1181 unsigned minIndex = 0;
1182 for (unsigned i=1; i < mdelayNodeVec.size(); i++)
1185 mii.maxLatency(mdelayNodeVec[i]->getOpCode());
1192 sdelayNodeVec.push_back(mdelayNodeVec[minIndex]);
1193 if (sdelayNodeVec.size() < ndelays) // avoid the last erase!
1194 mdelayNodeVec.erase(mdelayNodeVec.begin() + minIndex);
1199 // Remove the NOPs currently in delay slots from the graph.
1200 // Mark instructions specified in sdelayNodeVec to replace them.
1201 // If not enough useful instructions were found, mark the NOPs to be used
1202 // for filling delay slots, otherwise, otherwise just discard them.
1204 static void ReplaceNopsWithUsefulInstr(SchedulingManager& S,
1205 SchedGraphNode* node,
1206 vector<SchedGraphNode*> sdelayNodeVec,
1209 vector<SchedGraphNode*> nopNodeVec; // this will hold unused NOPs
1210 const TargetInstrInfo& mii = S.getInstrInfo();
1211 const MachineInstr* brInstr = node->getMachineInstr();
1212 unsigned ndelays= mii.getNumDelaySlots(brInstr->getOpCode());
1213 assert(ndelays > 0 && "Unnecessary call to replace NOPs");
1215 // Remove the NOPs currently in delay slots from the graph.
1216 // If not enough useful instructions were found, use the NOPs to
1217 // fill delay slots, otherwise, just discard them.
1219 unsigned int firstDelaySlotIdx = node->getOrigIndexInBB() + 1;
1220 MachineBasicBlock& MBB = node->getMachineBasicBlock();
1221 assert(MBB[firstDelaySlotIdx - 1] == brInstr &&
1222 "Incorrect instr. index in basic block for brInstr");
1224 // First find all useful instructions already in the delay slots
1225 // and USE THEM. We'll throw away the unused alternatives below
1227 for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
1228 if (! mii.isNop(MBB[i]->getOpCode()))
1229 sdelayNodeVec.insert(sdelayNodeVec.begin(),
1230 graph->getGraphNodeForInstr(MBB[i]));
1232 // Then find the NOPs and keep only as many as are needed.
1233 // Put the rest in nopNodeVec to be deleted.
1234 for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
1235 if (mii.isNop(MBB[i]->getOpCode()))
1236 if (sdelayNodeVec.size() < ndelays)
1237 sdelayNodeVec.push_back(graph->getGraphNodeForInstr(MBB[i]));
1240 nopNodeVec.push_back(graph->getGraphNodeForInstr(MBB[i]));
1242 //remove the MI from the Machine Code For Instruction
1243 TerminatorInst *TI = MBB.getBasicBlock()->getTerminator();
1244 MachineCodeForInstruction& llvmMvec =
1245 MachineCodeForInstruction::get((Instruction *)TI);
1247 for(MachineCodeForInstruction::iterator mciI=llvmMvec.begin(),
1248 mciE=llvmMvec.end(); mciI!=mciE; ++mciI){
1250 llvmMvec.erase(mciI);
1254 assert(sdelayNodeVec.size() >= ndelays);
1256 // If some delay slots were already filled, throw away that many new choices
1257 if (sdelayNodeVec.size() > ndelays)
1258 sdelayNodeVec.resize(ndelays);
1260 // Mark the nodes chosen for delay slots. This removes them from the graph.
1261 for (unsigned i=0; i < sdelayNodeVec.size(); i++)
1262 MarkNodeForDelaySlot(S, graph, sdelayNodeVec[i], node, true);
1264 // And remove the unused NOPs from the graph.
1265 for (unsigned i=0; i < nopNodeVec.size(); i++)
1266 graph->eraseIncidentEdges(nopNodeVec[i], /*addDummyEdges*/ true);
1270 // For all delayed instructions, choose instructions to put in the delay
1271 // slots and pull those out of the graph. Mark them for the delay slots
1272 // in the DelaySlotInfo object for that graph node. If no useful work
1273 // is found for a delay slot, use the NOP that is currently in that slot.
1275 // We try to fill the delay slots with useful work for all instructions
1276 // EXCEPT CALLS AND RETURNS.
1277 // For CALLs and RETURNs, it is nearly always possible to use one of the
1278 // call sequence instrs and putting anything else in the delay slot could be
1279 // suboptimal. Also, it complicates generating the calling sequence code in
1283 ChooseInstructionsForDelaySlots(SchedulingManager& S, MachineBasicBlock &MBB,
1286 const TargetInstrInfo& mii = S.getInstrInfo();
1288 Instruction *termInstr = (Instruction*)MBB.getBasicBlock()->getTerminator();
1289 MachineCodeForInstruction &termMvec=MachineCodeForInstruction::get(termInstr);
1290 vector<SchedGraphNode*> delayNodeVec;
1291 const MachineInstr* brInstr = NULL;
1293 if (termInstr->getOpcode() != Instruction::Ret)
1295 // To find instructions that need delay slots without searching the full
1296 // machine code, we assume that the only delayed instructions are CALLs
1297 // or instructions generated for the terminator inst.
1298 // Find the first branch instr in the sequence of machine instrs for term
1301 while (first < termMvec.size() &&
1302 ! mii.isBranch(termMvec[first]->getOpCode()))
1306 assert(first < termMvec.size() &&
1307 "No branch instructions for BR? Ok, but weird! Delete assertion.");
1309 brInstr = (first < termMvec.size())? termMvec[first] : NULL;
1311 // Compute a vector of the nodes chosen for delay slots and then
1312 // mark delay slots to replace NOPs with these useful instructions.
1314 if (brInstr != NULL)
1316 SchedGraphNode* brNode = graph->getGraphNodeForInstr(brInstr);
1317 FindUsefulInstructionsForDelaySlots(S, brNode, delayNodeVec);
1318 ReplaceNopsWithUsefulInstr(S, brNode, delayNodeVec, graph);
1322 // Also mark delay slots for other delayed instructions to hold NOPs.
1323 // Simply passing in an empty delayNodeVec will have this effect.
1325 delayNodeVec.clear();
1326 for (unsigned i=0; i < MBB.size(); ++i)
1327 if (MBB[i] != brInstr &&
1328 mii.getNumDelaySlots(MBB[i]->getOpCode()) > 0)
1330 SchedGraphNode* node = graph->getGraphNodeForInstr(MBB[i]);
1331 ReplaceNopsWithUsefulInstr(S, node, delayNodeVec, graph);
1337 // Schedule the delayed branch and its delay slots
1340 DelaySlotInfo::scheduleDelayedNode(SchedulingManager& S)
1342 assert(delayedNodeSlotNum < S.nslots && "Illegal slot for branch");
1343 assert(S.isched.getInstr(delayedNodeSlotNum, delayedNodeCycle) == NULL
1344 && "Slot for branch should be empty");
1346 unsigned int nextSlot = delayedNodeSlotNum;
1347 cycles_t nextTime = delayedNodeCycle;
1349 S.scheduleInstr(brNode, nextSlot, nextTime);
1351 for (unsigned d=0; d < ndelays; d++)
1354 if (nextSlot == S.nslots)
1360 // Find the first feasible instruction for this delay slot
1361 // Note that we only check for issue restrictions here.
1362 // We do *not* check for flow dependences but rely on pipeline
1363 // interlocks to resolve them. Machines without interlocks
1364 // will require this code to be modified.
1365 for (unsigned i=0; i < delayNodeVec.size(); i++)
1367 const SchedGraphNode* dnode = delayNodeVec[i];
1368 if ( ! S.isScheduled(dnode)
1369 && S.schedInfo.instrCanUseSlot(dnode->getOpCode(), nextSlot)
1370 && instrIsFeasible(S, dnode->getOpCode()))
1372 assert(S.getInstrInfo().hasOperandInterlock(dnode->getOpCode())
1373 && "Instructions without interlocks not yet supported "
1374 "when filling branch delay slots");
1375 S.scheduleInstr(dnode, nextSlot, nextTime);
1381 // Update current time if delay slots overflowed into later cycles.
1382 // Do this here because we know exactly which cycle is the last cycle
1383 // that contains delay slots. The next loop doesn't compute that.
1384 if (nextTime > S.getTime())
1385 S.updateTime(nextTime);
1387 // Now put any remaining instructions in the unfilled delay slots.
1388 // This could lead to suboptimal performance but needed for correctness.
1389 nextSlot = delayedNodeSlotNum;
1390 nextTime = delayedNodeCycle;
1391 for (unsigned i=0; i < delayNodeVec.size(); i++)
1392 if (! S.isScheduled(delayNodeVec[i]))
1394 do { // find the next empty slot
1396 if (nextSlot == S.nslots)
1401 } while (S.isched.getInstr(nextSlot, nextTime) != NULL);
1403 S.scheduleInstr(delayNodeVec[i], nextSlot, nextTime);
1411 // Check if the instruction would conflict with instructions already
1412 // chosen for the current cycle
1415 ConflictsWithChoices(const SchedulingManager& S,
1416 MachineOpCode opCode)
1418 // Check if the instruction must issue by itself, and some feasible
1419 // choices have already been made for this cycle
1420 if (S.getNumChoices() > 0 && S.schedInfo.isSingleIssue(opCode))
1423 // For each class that opCode belongs to, check if there are too many
1424 // instructions of that class.
1426 const InstrSchedClass sc = S.schedInfo.getSchedClass(opCode);
1427 return (S.getNumChoicesInClass(sc) == S.schedInfo.getMaxIssueForClass(sc));
1431 //************************* External Functions *****************************/
1434 //---------------------------------------------------------------------------
1435 // Function: ViolatesMinimumGap
1438 // Check minimum gap requirements relative to instructions scheduled in
1440 // Note that we do not need to consider `nextEarliestIssueTime' here because
1441 // that is also captured in the earliest start times for each opcode.
1442 //---------------------------------------------------------------------------
1445 ViolatesMinimumGap(const SchedulingManager& S,
1446 MachineOpCode opCode,
1447 const cycles_t inCycle)
1449 return (inCycle < S.getEarliestStartTimeForOp(opCode));
1453 //---------------------------------------------------------------------------
1454 // Function: instrIsFeasible
1457 // Check if any issue restrictions would prevent the instruction from
1458 // being issued in the current cycle
1459 //---------------------------------------------------------------------------
1462 instrIsFeasible(const SchedulingManager& S,
1463 MachineOpCode opCode)
1465 // skip the instruction if it cannot be issued due to issue restrictions
1466 // caused by previously issued instructions
1467 if (ViolatesMinimumGap(S, opCode, S.getTime()))
1470 // skip the instruction if it cannot be issued due to issue restrictions
1471 // caused by previously chosen instructions for the current cycle
1472 if (ConflictsWithChoices(S, opCode))
1478 //---------------------------------------------------------------------------
1479 // Function: ScheduleInstructionsWithSSA
1482 // Entry point for instruction scheduling on SSA form.
1483 // Schedules the machine instructions generated by instruction selection.
1484 // Assumes that register allocation has not been done, i.e., operands
1485 // are still in SSA form.
1486 //---------------------------------------------------------------------------
1489 class InstructionSchedulingWithSSA : public FunctionPass {
1490 const TargetMachine ⌖
1492 inline InstructionSchedulingWithSSA(const TargetMachine &T) : target(T) {}
1494 const char *getPassName() const { return "Instruction Scheduling"; }
1496 // getAnalysisUsage - We use LiveVarInfo...
1497 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1498 AU.addRequired<FunctionLiveVarInfo>();
1499 AU.setPreservesCFG();
1502 bool runOnFunction(Function &F);
1504 } // end anonymous namespace
1507 bool InstructionSchedulingWithSSA::runOnFunction(Function &F)
1509 SchedGraphSet graphSet(&F, target);
1511 if (SchedDebugLevel >= Sched_PrintSchedGraphs)
1513 cerr << "\n*** SCHEDULING GRAPHS FOR INSTRUCTION SCHEDULING\n";
1517 for (SchedGraphSet::const_iterator GI=graphSet.begin(), GE=graphSet.end();
1520 SchedGraph* graph = (*GI);
1521 MachineBasicBlock &MBB = graph->getBasicBlock();
1523 if (SchedDebugLevel >= Sched_PrintSchedTrace)
1524 cerr << "\n*** TRACE OF INSTRUCTION SCHEDULING OPERATIONS\n\n";
1527 SchedPriorities schedPrio(&F, graph,getAnalysis<FunctionLiveVarInfo>());
1528 SchedulingManager S(target, graph, schedPrio);
1530 ChooseInstructionsForDelaySlots(S, MBB, graph); // modifies graph
1531 ForwardListSchedule(S); // computes schedule in S
1532 RecordSchedule(MBB, S); // records schedule in BB
1535 if (SchedDebugLevel >= Sched_PrintMachineCode)
1537 cerr << "\n*** Machine instructions after INSTRUCTION SCHEDULING\n";
1538 MachineFunction::get(&F).dump();
1545 Pass *createInstructionSchedulingWithSSAPass(const TargetMachine &tgt) {
1546 return new InstructionSchedulingWithSSA(tgt);