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/MachineCodeForMethod.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 "llvm/Instruction.h"
16 #include "Support/CommandLine.h"
21 SchedDebugLevel_t SchedDebugLevel;
23 static cl::Enum<enum SchedDebugLevel_t> Opt(SchedDebugLevel,"dsched",cl::Hidden,
24 "enable instruction scheduling debugging information",
25 clEnumValN(Sched_NoDebugInfo, "n", "disable debug output"),
26 clEnumValN(Sched_Disable, "off", "disable instruction scheduling"),
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"), 0);
32 //************************* Internal Data Types *****************************/
35 class SchedulingManager;
38 //----------------------------------------------------------------------
41 // Represents a group of instructions scheduled to be issued
43 //----------------------------------------------------------------------
45 class InstrGroup: public NonCopyable {
47 inline const SchedGraphNode* operator[](unsigned int slotNum) const {
48 assert(slotNum < group.size());
49 return group[slotNum];
53 friend class InstrSchedule;
55 inline void addInstr(const SchedGraphNode* node, unsigned int slotNum) {
56 assert(slotNum < group.size());
57 group[slotNum] = node;
60 /*ctor*/ InstrGroup(unsigned int nslots)
61 : group(nslots, NULL) {}
63 /*ctor*/ InstrGroup(); // disable: DO NOT IMPLEMENT
66 vector<const SchedGraphNode*> group;
70 //----------------------------------------------------------------------
71 // class ScheduleIterator:
73 // Iterates over the machine instructions in the for a single basic block.
74 // The schedule is represented by an InstrSchedule object.
75 //----------------------------------------------------------------------
77 template<class _NodeType>
78 class ScheduleIterator: public std::forward_iterator<_NodeType, ptrdiff_t> {
82 const InstrSchedule& S;
84 typedef ScheduleIterator<_NodeType> _Self;
86 /*ctor*/ inline ScheduleIterator(const InstrSchedule& _schedule,
89 : cycleNum(_cycleNum), slotNum(_slotNum), S(_schedule) {
93 /*ctor*/ inline ScheduleIterator(const _Self& x)
94 : cycleNum(x.cycleNum), slotNum(x.slotNum), S(x.S) {}
96 inline bool operator==(const _Self& x) const {
97 return (slotNum == x.slotNum && cycleNum== x.cycleNum && &S==&x.S);
100 inline bool operator!=(const _Self& x) const { return !operator==(x); }
102 inline _NodeType* operator*() const {
103 assert(cycleNum < S.groups.size());
104 return (*S.groups[cycleNum])[slotNum];
106 inline _NodeType* operator->() const { return operator*(); }
108 _Self& operator++(); // Preincrement
109 inline _Self operator++(int) { // Postincrement
110 _Self tmp(*this); ++*this; return tmp;
113 static _Self begin(const InstrSchedule& _schedule);
114 static _Self end( const InstrSchedule& _schedule);
117 inline _Self& operator=(const _Self& x); // DISABLE -- DO NOT IMPLEMENT
118 void skipToNextInstr();
122 //----------------------------------------------------------------------
123 // class InstrSchedule:
125 // Represents the schedule of machine instructions for a single basic block.
126 //----------------------------------------------------------------------
128 class InstrSchedule: public NonCopyable {
130 const unsigned int nslots;
131 unsigned int numInstr;
132 vector<InstrGroup*> groups; // indexed by cycle number
133 vector<cycles_t> startTime; // indexed by node id
136 typedef ScheduleIterator<SchedGraphNode> iterator;
137 typedef ScheduleIterator<const SchedGraphNode> const_iterator;
140 const_iterator begin() const;
142 const_iterator end() const;
144 public: // constructors and destructor
145 /*ctor*/ InstrSchedule (unsigned int _nslots,
146 unsigned int _numNodes);
147 /*dtor*/ ~InstrSchedule ();
149 public: // accessor functions to query chosen schedule
150 const SchedGraphNode* getInstr (unsigned int slotNum,
152 const InstrGroup* igroup = this->getIGroup(c);
153 return (igroup == NULL)? NULL : (*igroup)[slotNum];
156 inline InstrGroup* getIGroup (cycles_t c) {
157 if ((unsigned)c >= groups.size())
159 if (groups[c] == NULL)
160 groups[c] = new InstrGroup(nslots);
164 inline const InstrGroup* getIGroup (cycles_t c) const {
165 assert((unsigned)c < groups.size());
169 inline cycles_t getStartTime (unsigned int nodeId) const {
170 assert(nodeId < startTime.size());
171 return startTime[nodeId];
174 unsigned int getNumInstructions() const {
178 inline void scheduleInstr (const SchedGraphNode* node,
179 unsigned int slotNum,
181 InstrGroup* igroup = this->getIGroup(cycle);
182 assert((*igroup)[slotNum] == NULL && "Slot already filled?");
183 igroup->addInstr(node, slotNum);
184 assert(node->getNodeId() < startTime.size());
185 startTime[node->getNodeId()] = cycle;
190 friend class iterator;
191 friend class const_iterator;
192 /*ctor*/ InstrSchedule (); // Disable: DO NOT IMPLEMENT.
197 InstrSchedule::InstrSchedule(unsigned int _nslots, unsigned int _numNodes)
200 groups(2 * _numNodes / _nslots), // 2 x lower-bound for #cycles
201 startTime(_numNodes, (cycles_t) -1) // set all to -1
207 InstrSchedule::~InstrSchedule()
209 for (unsigned c=0, NC=groups.size(); c < NC; c++)
210 if (groups[c] != NULL)
211 delete groups[c]; // delete InstrGroup objects
215 template<class _NodeType>
218 ScheduleIterator<_NodeType>::skipToNextInstr()
220 while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
221 ++cycleNum; // skip cycles with no instructions
223 while (cycleNum < S.groups.size() &&
224 (*S.groups[cycleNum])[slotNum] == NULL)
227 if (slotNum == S.nslots)
231 while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
232 ++cycleNum; // skip cycles with no instructions
237 template<class _NodeType>
239 ScheduleIterator<_NodeType>&
240 ScheduleIterator<_NodeType>::operator++() // Preincrement
243 if (slotNum == S.nslots)
252 template<class _NodeType>
253 ScheduleIterator<_NodeType>
254 ScheduleIterator<_NodeType>::begin(const InstrSchedule& _schedule)
256 return _Self(_schedule, 0, 0);
259 template<class _NodeType>
260 ScheduleIterator<_NodeType>
261 ScheduleIterator<_NodeType>::end(const InstrSchedule& _schedule)
263 return _Self(_schedule, _schedule.groups.size(), 0);
266 InstrSchedule::iterator
267 InstrSchedule::begin()
269 return iterator::begin(*this);
272 InstrSchedule::const_iterator
273 InstrSchedule::begin() const
275 return const_iterator::begin(*this);
278 InstrSchedule::iterator
281 return iterator::end(*this);
284 InstrSchedule::const_iterator
285 InstrSchedule::end() const
287 return const_iterator::end( *this);
291 //----------------------------------------------------------------------
292 // class DelaySlotInfo:
294 // Record information about delay slots for a single branch instruction.
295 // Delay slots are simply indexed by slot number 1 ... numDelaySlots
296 //----------------------------------------------------------------------
298 class DelaySlotInfo: public NonCopyable {
300 const SchedGraphNode* brNode;
301 unsigned int ndelays;
302 vector<const SchedGraphNode*> delayNodeVec;
303 cycles_t delayedNodeCycle;
304 unsigned int delayedNodeSlotNum;
307 /*ctor*/ DelaySlotInfo (const SchedGraphNode* _brNode,
309 : brNode(_brNode), ndelays(_ndelays),
310 delayedNodeCycle(0), delayedNodeSlotNum(0) {}
312 inline unsigned getNumDelays () {
316 inline const vector<const SchedGraphNode*>& getDelayNodeVec() {
320 inline void addDelayNode (const SchedGraphNode* node) {
321 delayNodeVec.push_back(node);
322 assert(delayNodeVec.size() <= ndelays && "Too many delay slot instrs!");
325 inline void recordChosenSlot (cycles_t cycle, unsigned slotNum) {
326 delayedNodeCycle = cycle;
327 delayedNodeSlotNum = slotNum;
330 unsigned scheduleDelayedNode (SchedulingManager& S);
334 //----------------------------------------------------------------------
335 // class SchedulingManager:
337 // Represents the schedule of machine instructions for a single basic block.
338 //----------------------------------------------------------------------
340 class SchedulingManager: public NonCopyable {
341 public: // publicly accessible data members
342 const unsigned int nslots;
343 const MachineSchedInfo& schedInfo;
344 SchedPriorities& schedPrio;
345 InstrSchedule isched;
348 unsigned int totalInstrCount;
350 cycles_t nextEarliestIssueTime; // next cycle we can issue
351 vector<std::hash_set<const SchedGraphNode*> > choicesForSlot; // indexed by slot#
352 vector<const SchedGraphNode*> choiceVec; // indexed by node ptr
353 vector<int> numInClass; // indexed by sched class
354 vector<cycles_t> nextEarliestStartTime; // indexed by opCode
355 std::hash_map<const SchedGraphNode*, DelaySlotInfo*> delaySlotInfoForBranches;
356 // indexed by branch node ptr
359 SchedulingManager(const TargetMachine& _target, const SchedGraph* graph,
360 SchedPriorities& schedPrio);
361 ~SchedulingManager() {
362 for (std::hash_map<const SchedGraphNode*,
363 DelaySlotInfo*>::iterator I = delaySlotInfoForBranches.begin(),
364 E = delaySlotInfoForBranches.end(); I != E; ++I)
368 //----------------------------------------------------------------------
369 // Simplify access to the machine instruction info
370 //----------------------------------------------------------------------
372 inline const MachineInstrInfo& getInstrInfo () const {
373 return schedInfo.getInstrInfo();
376 //----------------------------------------------------------------------
377 // Interface for checking and updating the current time
378 //----------------------------------------------------------------------
380 inline cycles_t getTime () const {
384 inline cycles_t getEarliestIssueTime() const {
385 return nextEarliestIssueTime;
388 inline cycles_t getEarliestStartTimeForOp(MachineOpCode opCode) const {
389 assert(opCode < (int) nextEarliestStartTime.size());
390 return nextEarliestStartTime[opCode];
393 // Update current time to specified cycle
394 inline void updateTime (cycles_t c) {
396 schedPrio.updateTime(c);
399 //----------------------------------------------------------------------
400 // Functions to manage the choices for the current cycle including:
401 // -- a vector of choices by priority (choiceVec)
402 // -- vectors of the choices for each instruction slot (choicesForSlot[])
403 // -- number of choices in each sched class, used to check issue conflicts
404 // between choices for a single cycle
405 //----------------------------------------------------------------------
407 inline unsigned int getNumChoices () const {
408 return choiceVec.size();
411 inline unsigned getNumChoicesInClass (const InstrSchedClass& sc) const {
412 assert(sc < (int) numInClass.size() && "Invalid op code or sched class!");
413 return numInClass[sc];
416 inline const SchedGraphNode* getChoice(unsigned int i) const {
417 // assert(i < choiceVec.size()); don't check here.
421 inline std::hash_set<const SchedGraphNode*>& getChoicesForSlot(unsigned slotNum) {
422 assert(slotNum < nslots);
423 return choicesForSlot[slotNum];
426 inline void addChoice (const SchedGraphNode* node) {
427 // Append the instruction to the vector of choices for current cycle.
428 // Increment numInClass[c] for the sched class to which the instr belongs.
429 choiceVec.push_back(node);
430 const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpCode());
431 assert(sc < (int) numInClass.size());
435 inline void addChoiceToSlot (unsigned int slotNum,
436 const SchedGraphNode* node) {
437 // Add the instruction to the choice set for the specified slot
438 assert(slotNum < nslots);
439 choicesForSlot[slotNum].insert(node);
442 inline void resetChoices () {
444 for (unsigned int s=0; s < nslots; s++)
445 choicesForSlot[s].clear();
446 for (unsigned int c=0; c < numInClass.size(); c++)
450 //----------------------------------------------------------------------
451 // Code to query and manage the partial instruction schedule so far
452 //----------------------------------------------------------------------
454 inline unsigned int getNumScheduled () const {
455 return isched.getNumInstructions();
458 inline unsigned int getNumUnscheduled() const {
459 return totalInstrCount - isched.getNumInstructions();
462 inline bool isScheduled (const SchedGraphNode* node) const {
463 return (isched.getStartTime(node->getNodeId()) >= 0);
466 inline void scheduleInstr (const SchedGraphNode* node,
467 unsigned int slotNum,
470 assert(! isScheduled(node) && "Instruction already scheduled?");
472 // add the instruction to the schedule
473 isched.scheduleInstr(node, slotNum, cycle);
475 // update the earliest start times of all nodes that conflict with `node'
476 // and the next-earliest time anything can issue if `node' causes bubbles
477 updateEarliestStartTimes(node, cycle);
479 // remove the instruction from the choice sets for all slots
480 for (unsigned s=0; s < nslots; s++)
481 choicesForSlot[s].erase(node);
483 // and decrement the instr count for the sched class to which it belongs
484 const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpCode());
485 assert(sc < (int) numInClass.size());
489 //----------------------------------------------------------------------
490 // Create and retrieve delay slot info for delayed instructions
491 //----------------------------------------------------------------------
493 inline DelaySlotInfo* getDelaySlotInfoForInstr(const SchedGraphNode* bn,
494 bool createIfMissing=false)
496 std::hash_map<const SchedGraphNode*, DelaySlotInfo*>::const_iterator
497 I = delaySlotInfoForBranches.find(bn);
498 if (I != delaySlotInfoForBranches.end())
501 if (!createIfMissing) return 0;
503 DelaySlotInfo *dinfo =
504 new DelaySlotInfo(bn, getInstrInfo().getNumDelaySlots(bn->getOpCode()));
505 return delaySlotInfoForBranches[bn] = dinfo;
509 SchedulingManager(); // DISABLED: DO NOT IMPLEMENT
510 void updateEarliestStartTimes(const SchedGraphNode* node, cycles_t schedTime);
515 SchedulingManager::SchedulingManager(const TargetMachine& target,
516 const SchedGraph* graph,
517 SchedPriorities& _schedPrio)
518 : nslots(target.getSchedInfo().getMaxNumIssueTotal()),
519 schedInfo(target.getSchedInfo()),
520 schedPrio(_schedPrio),
521 isched(nslots, graph->getNumNodes()),
522 totalInstrCount(graph->getNumNodes() - 2),
523 nextEarliestIssueTime(0),
524 choicesForSlot(nslots),
525 numInClass(target.getSchedInfo().getNumSchedClasses(), 0), // set all to 0
526 nextEarliestStartTime(target.getInstrInfo().getNumRealOpCodes(),
527 (cycles_t) 0) // set all to 0
531 // Note that an upper bound on #choices for each slot is = nslots since
532 // we use this vector to hold a feasible set of instructions, and more
533 // would be infeasible. Reserve that much memory since it is probably small.
534 for (unsigned int i=0; i < nslots; i++)
535 choicesForSlot[i].resize(nslots);
540 SchedulingManager::updateEarliestStartTimes(const SchedGraphNode* node,
543 if (schedInfo.numBubblesAfter(node->getOpCode()) > 0)
544 { // Update next earliest time before which *nothing* can issue.
545 nextEarliestIssueTime = std::max(nextEarliestIssueTime,
546 curTime + 1 + schedInfo.numBubblesAfter(node->getOpCode()));
549 const vector<MachineOpCode>*
550 conflictVec = schedInfo.getConflictList(node->getOpCode());
552 if (conflictVec != NULL)
553 for (unsigned i=0; i < conflictVec->size(); i++)
555 MachineOpCode toOp = (*conflictVec)[i];
556 cycles_t est = schedTime + schedInfo.getMinIssueGap(node->getOpCode(),
558 assert(toOp < (int) nextEarliestStartTime.size());
559 if (nextEarliestStartTime[toOp] < est)
560 nextEarliestStartTime[toOp] = est;
564 //************************* Internal Functions *****************************/
568 AssignInstructionsToSlots(class SchedulingManager& S, unsigned maxIssue)
570 // find the slot to start from, in the current cycle
571 unsigned int startSlot = 0;
572 cycles_t curTime = S.getTime();
574 assert(maxIssue > 0 && maxIssue <= S.nslots - startSlot);
576 // If only one instruction can be issued, do so.
578 for (unsigned s=startSlot; s < S.nslots; s++)
579 if (S.getChoicesForSlot(s).size() > 0)
580 {// found the one instruction
581 S.scheduleInstr(*S.getChoicesForSlot(s).begin(), s, curTime);
585 // Otherwise, choose from the choices for each slot
587 InstrGroup* igroup = S.isched.getIGroup(S.getTime());
588 assert(igroup != NULL && "Group creation failed?");
590 // Find a slot that has only a single choice, and take it.
591 // If all slots have 0 or multiple choices, pick the first slot with
592 // choices and use its last instruction (just to avoid shifting the vector).
594 for (numIssued = 0; numIssued < maxIssue; numIssued++)
597 for (unsigned s=startSlot; s < S.nslots; s++)
598 if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() == 1)
600 chosenSlot = (int) s;
604 if (chosenSlot == -1)
605 for (unsigned s=startSlot; s < S.nslots; s++)
606 if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() > 0)
608 chosenSlot = (int) s;
612 if (chosenSlot != -1)
613 { // Insert the chosen instr in the chosen slot and
614 // erase it from all slots.
615 const SchedGraphNode* node= *S.getChoicesForSlot(chosenSlot).begin();
616 S.scheduleInstr(node, chosenSlot, curTime);
620 assert(numIssued > 0 && "Should not happen when maxIssue > 0!");
625 // For now, just assume we are scheduling within a single basic block.
626 // Get the machine instruction vector for the basic block and clear it,
627 // then append instructions in scheduled order.
628 // Also, re-insert the dummy PHI instructions that were at the beginning
629 // of the basic block, since they are not part of the schedule.
632 RecordSchedule(const BasicBlock* bb, const SchedulingManager& S)
634 MachineCodeForBasicBlock& mvec = bb->getMachineInstrVec();
635 const MachineInstrInfo& mii = S.schedInfo.getInstrInfo();
638 // Lets make sure we didn't lose any instructions, except possibly
639 // some NOPs from delay slots. Also, PHIs are not included in the schedule.
640 unsigned numInstr = 0;
641 for (MachineCodeForBasicBlock::iterator I=mvec.begin(); I != mvec.end(); ++I)
642 if (! mii.isNop((*I)->getOpCode()) &&
643 ! mii.isDummyPhiInstr((*I)->getOpCode()))
645 assert(S.isched.getNumInstructions() >= numInstr &&
646 "Lost some non-NOP instructions during scheduling!");
649 if (S.isched.getNumInstructions() == 0)
650 return; // empty basic block!
652 // First find the dummy instructions at the start of the basic block
653 MachineCodeForBasicBlock::iterator I = mvec.begin();
654 for ( ; I != mvec.end(); ++I)
655 if (! mii.isDummyPhiInstr((*I)->getOpCode()))
658 // Erase all except the dummy PHI instructions from mvec, and
659 // pre-allocate create space for the ones we will put back in.
660 mvec.erase(I, mvec.end());
662 InstrSchedule::const_iterator NIend = S.isched.end();
663 for (InstrSchedule::const_iterator NI = S.isched.begin(); NI != NIend; ++NI)
664 mvec.push_back(const_cast<MachineInstr*>((*NI)->getMachineInstr()));
670 MarkSuccessorsReady(SchedulingManager& S, const SchedGraphNode* node)
672 // Check if any successors are now ready that were not already marked
673 // ready before, and that have not yet been scheduled.
675 for (sg_succ_const_iterator SI = succ_begin(node); SI !=succ_end(node); ++SI)
676 if (! (*SI)->isDummyNode()
677 && ! S.isScheduled(*SI)
678 && ! S.schedPrio.nodeIsReady(*SI))
679 {// successor not scheduled and not marked ready; check *its* preds.
681 bool succIsReady = true;
682 for (sg_pred_const_iterator P=pred_begin(*SI); P != pred_end(*SI); ++P)
683 if (! (*P)->isDummyNode()
684 && ! S.isScheduled(*P))
690 if (succIsReady) // add the successor to the ready list
691 S.schedPrio.insertReady(*SI);
696 // Choose up to `nslots' FEASIBLE instructions and assign each
697 // instruction to all possible slots that do not violate feasibility.
698 // FEASIBLE means it should be guaranteed that the set
699 // of chosen instructions can be issued in a single group.
702 // maxIssue : total number of feasible instructions
703 // S.choicesForSlot[i=0..nslots] : set of instructions feasible in slot i
706 FindSlotChoices(SchedulingManager& S,
707 DelaySlotInfo*& getDelaySlotInfo)
709 // initialize result vectors to empty
712 // find the slot to start from, in the current cycle
713 unsigned int startSlot = 0;
714 InstrGroup* igroup = S.isched.getIGroup(S.getTime());
715 for (int s = S.nslots - 1; s >= 0; s--)
716 if ((*igroup)[s] != NULL)
722 // Make sure we pick at most one instruction that would break the group.
723 // Also, if we do pick one, remember which it was.
724 unsigned int indexForBreakingNode = S.nslots;
725 unsigned int indexForDelayedInstr = S.nslots;
726 DelaySlotInfo* delaySlotInfo = NULL;
728 getDelaySlotInfo = NULL;
730 // Choose instructions in order of priority.
731 // Add choices to the choice vector in the SchedulingManager class as
732 // we choose them so that subsequent choices will be correctly tested
733 // for feasibility, w.r.t. higher priority choices for the same cycle.
735 while (S.getNumChoices() < S.nslots - startSlot)
737 const SchedGraphNode* nextNode=S.schedPrio.getNextHighest(S,S.getTime());
738 if (nextNode == NULL)
739 break; // no more instructions for this cycle
741 if (S.getInstrInfo().getNumDelaySlots(nextNode->getOpCode()) > 0)
743 delaySlotInfo = S.getDelaySlotInfoForInstr(nextNode);
744 if (delaySlotInfo != NULL)
746 if (indexForBreakingNode < S.nslots)
747 // cannot issue a delayed instr in the same cycle as one
748 // that breaks the issue group or as another delayed instr
751 indexForDelayedInstr = S.getNumChoices();
754 else if (S.schedInfo.breaksIssueGroup(nextNode->getOpCode()))
756 if (indexForBreakingNode < S.nslots)
757 // have a breaking instruction already so throw this one away
760 indexForBreakingNode = S.getNumChoices();
763 if (nextNode != NULL)
765 S.addChoice(nextNode);
767 if (S.schedInfo.isSingleIssue(nextNode->getOpCode()))
769 assert(S.getNumChoices() == 1 &&
770 "Prioritizer returned invalid instr for this cycle!");
775 if (indexForDelayedInstr < S.nslots)
776 break; // leave the rest for delay slots
779 assert(S.getNumChoices() <= S.nslots);
780 assert(! (indexForDelayedInstr < S.nslots &&
781 indexForBreakingNode < S.nslots) && "Cannot have both in a cycle");
783 // Assign each chosen instruction to all possible slots for that instr.
784 // But if only one instruction was chosen, put it only in the first
785 // feasible slot; no more analysis will be needed.
787 if (indexForDelayedInstr >= S.nslots &&
788 indexForBreakingNode >= S.nslots)
789 { // No instructions that break the issue group or that have delay slots.
790 // This is the common case, so handle it separately for efficiency.
792 if (S.getNumChoices() == 1)
794 MachineOpCode opCode = S.getChoice(0)->getOpCode();
796 for (s=startSlot; s < S.nslots; s++)
797 if (S.schedInfo.instrCanUseSlot(opCode, s))
799 assert(s < S.nslots && "No feasible slot for this opCode?");
800 S.addChoiceToSlot(s, S.getChoice(0));
804 for (unsigned i=0; i < S.getNumChoices(); i++)
806 MachineOpCode opCode = S.getChoice(i)->getOpCode();
807 for (unsigned int s=startSlot; s < S.nslots; s++)
808 if (S.schedInfo.instrCanUseSlot(opCode, s))
809 S.addChoiceToSlot(s, S.getChoice(i));
813 else if (indexForDelayedInstr < S.nslots)
815 // There is an instruction that needs delay slots.
816 // Try to assign that instruction to a higher slot than any other
817 // instructions in the group, so that its delay slots can go
821 assert(indexForDelayedInstr == S.getNumChoices() - 1 &&
822 "Instruction with delay slots should be last choice!");
823 assert(delaySlotInfo != NULL && "No delay slot info for instr?");
825 const SchedGraphNode* delayedNode = S.getChoice(indexForDelayedInstr);
826 MachineOpCode delayOpCode = delayedNode->getOpCode();
827 unsigned ndelays= S.getInstrInfo().getNumDelaySlots(delayOpCode);
829 unsigned delayedNodeSlot = S.nslots;
832 // Find the last possible slot for the delayed instruction that leaves
833 // at least `d' slots vacant after it (d = #delay slots)
834 for (int s = S.nslots-ndelays-1; s >= (int) startSlot; s--)
835 if (S.schedInfo.instrCanUseSlot(delayOpCode, s))
841 highestSlotUsed = -1;
842 for (unsigned i=0; i < S.getNumChoices() - 1; i++)
844 // Try to assign every other instruction to a lower numbered
845 // slot than delayedNodeSlot.
846 MachineOpCode opCode =S.getChoice(i)->getOpCode();
847 bool noSlotFound = true;
849 for (s=startSlot; s < delayedNodeSlot; s++)
850 if (S.schedInfo.instrCanUseSlot(opCode, s))
852 S.addChoiceToSlot(s, S.getChoice(i));
856 // No slot before `delayedNodeSlot' was found for this opCode
857 // Use a later slot, and allow some delay slots to fall in
860 for ( ; s < S.nslots; s++)
861 if (S.schedInfo.instrCanUseSlot(opCode, s))
863 S.addChoiceToSlot(s, S.getChoice(i));
867 assert(s < S.nslots && "No feasible slot for instruction?");
869 highestSlotUsed = std::max(highestSlotUsed, (int) s);
872 assert(highestSlotUsed <= (int) S.nslots-1 && "Invalid slot used?");
874 // We will put the delayed node in the first slot after the
875 // highest slot used. But we just mark that for now, and
876 // schedule it separately because we want to schedule the delay
877 // slots for the node at the same time.
878 cycles_t dcycle = S.getTime();
879 unsigned int dslot = highestSlotUsed + 1;
880 if (dslot == S.nslots)
885 delaySlotInfo->recordChosenSlot(dcycle, dslot);
886 getDelaySlotInfo = delaySlotInfo;
889 { // There is an instruction that breaks the issue group.
890 // For such an instruction, assign to the last possible slot in
891 // the current group, and then don't assign any other instructions
893 assert(indexForBreakingNode < S.nslots);
894 const SchedGraphNode* breakingNode=S.getChoice(indexForBreakingNode);
895 unsigned breakingSlot = INT_MAX;
896 unsigned int nslotsToUse = S.nslots;
898 // Find the last possible slot for this instruction.
899 for (int s = S.nslots-1; s >= (int) startSlot; s--)
900 if (S.schedInfo.instrCanUseSlot(breakingNode->getOpCode(), s))
905 assert(breakingSlot < S.nslots &&
906 "No feasible slot for `breakingNode'?");
908 // Higher priority instructions than the one that breaks the group:
909 // These can be assigned to all slots, but will be assigned only
910 // to earlier slots if possible.
912 i < S.getNumChoices() && i < indexForBreakingNode; i++)
914 MachineOpCode opCode =S.getChoice(i)->getOpCode();
916 // If a higher priority instruction cannot be assigned to
917 // any earlier slots, don't schedule the breaking instruction.
919 bool foundLowerSlot = false;
920 nslotsToUse = S.nslots; // May be modified in the loop
921 for (unsigned int s=startSlot; s < nslotsToUse; s++)
922 if (S.schedInfo.instrCanUseSlot(opCode, s))
924 if (breakingSlot < S.nslots && s < breakingSlot)
926 foundLowerSlot = true;
927 nslotsToUse = breakingSlot; // RESETS LOOP UPPER BOUND!
930 S.addChoiceToSlot(s, S.getChoice(i));
934 breakingSlot = INT_MAX; // disable breaking instr
937 // Assign the breaking instruction (if any) to a single slot
938 // Otherwise, just ignore the instruction. It will simply be
939 // scheduled in a later cycle.
940 if (breakingSlot < S.nslots)
942 S.addChoiceToSlot(breakingSlot, breakingNode);
943 nslotsToUse = breakingSlot;
946 nslotsToUse = S.nslots;
948 // For lower priority instructions than the one that breaks the
949 // group, only assign them to slots lower than the breaking slot.
950 // Otherwise, just ignore the instruction.
951 for (unsigned i=indexForBreakingNode+1; i < S.getNumChoices(); i++)
953 MachineOpCode opCode = S.getChoice(i)->getOpCode();
954 for (unsigned int s=startSlot; s < nslotsToUse; s++)
955 if (S.schedInfo.instrCanUseSlot(opCode, s))
956 S.addChoiceToSlot(s, S.getChoice(i));
958 } // endif (no delay slots and no breaking slots)
960 return S.getNumChoices();
965 ChooseOneGroup(SchedulingManager& S)
967 assert(S.schedPrio.getNumReady() > 0
968 && "Don't get here without ready instructions.");
970 cycles_t firstCycle = S.getTime();
971 DelaySlotInfo* getDelaySlotInfo = NULL;
973 // Choose up to `nslots' feasible instructions and their possible slots.
974 unsigned numIssued = FindSlotChoices(S, getDelaySlotInfo);
976 while (numIssued == 0)
978 S.updateTime(S.getTime()+1);
979 numIssued = FindSlotChoices(S, getDelaySlotInfo);
982 AssignInstructionsToSlots(S, numIssued);
984 if (getDelaySlotInfo != NULL)
985 numIssued += getDelaySlotInfo->scheduleDelayedNode(S);
987 // Print trace of scheduled instructions before newly ready ones
988 if (SchedDebugLevel >= Sched_PrintSchedTrace)
990 for (cycles_t c = firstCycle; c <= S.getTime(); c++)
992 cerr << " Cycle " << (long)c << " : Scheduled instructions:\n";
993 const InstrGroup* igroup = S.isched.getIGroup(c);
994 for (unsigned int s=0; s < S.nslots; s++)
997 if ((*igroup)[s] != NULL)
998 cerr << * ((*igroup)[s])->getMachineInstr() << "\n";
1010 ForwardListSchedule(SchedulingManager& S)
1013 const SchedGraphNode* node;
1015 S.schedPrio.initialize();
1017 while ((N = S.schedPrio.getNumReady()) > 0)
1019 cycles_t nextCycle = S.getTime();
1021 // Choose one group of instructions for a cycle, plus any delay slot
1022 // instructions (which may overflow into successive cycles).
1023 // This will advance S.getTime() to the last cycle in which
1024 // instructions are actually issued.
1026 unsigned numIssued = ChooseOneGroup(S);
1027 assert(numIssued > 0 && "Deadlock in list scheduling algorithm?");
1029 // Notify the priority manager of scheduled instructions and mark
1030 // any successors that may now be ready
1032 for (cycles_t c = nextCycle; c <= S.getTime(); c++)
1034 const InstrGroup* igroup = S.isched.getIGroup(c);
1035 for (unsigned int s=0; s < S.nslots; s++)
1036 if ((node = (*igroup)[s]) != NULL)
1038 S.schedPrio.issuedReadyNodeAt(S.getTime(), node);
1039 MarkSuccessorsReady(S, node);
1043 // Move to the next the next earliest cycle for which
1044 // an instruction can be issued, or the next earliest in which
1045 // one will be ready, or to the next cycle, whichever is latest.
1047 S.updateTime(std::max(S.getTime() + 1,
1048 std::max(S.getEarliestIssueTime(),
1049 S.schedPrio.getEarliestReadyTime())));
1054 //---------------------------------------------------------------------
1055 // Code for filling delay slots for delayed terminator instructions
1056 // (e.g., BRANCH and RETURN). Delay slots for non-terminator
1057 // instructions (e.g., CALL) are not handled here because they almost
1058 // always can be filled with instructions from the call sequence code
1059 // before a call. That's preferable because we incur many tradeoffs here
1060 // when we cannot find single-cycle instructions that can be reordered.
1061 //----------------------------------------------------------------------
1064 NodeCanFillDelaySlot(const SchedulingManager& S,
1065 const SchedGraphNode* node,
1066 const SchedGraphNode* brNode,
1067 bool nodeIsPredecessor)
1069 assert(! node->isDummyNode());
1071 // don't put a branch in the delay slot of another branch
1072 if (S.getInstrInfo().isBranch(node->getOpCode()))
1075 // don't put a single-issue instruction in the delay slot of a branch
1076 if (S.schedInfo.isSingleIssue(node->getOpCode()))
1079 // don't put a load-use dependence in the delay slot of a branch
1080 const MachineInstrInfo& mii = S.getInstrInfo();
1082 for (SchedGraphNode::const_iterator EI = node->beginInEdges();
1083 EI != node->endInEdges(); ++EI)
1084 if (! (*EI)->getSrc()->isDummyNode()
1085 && mii.isLoad((*EI)->getSrc()->getOpCode())
1086 && (*EI)->getDepType() == SchedGraphEdge::CtrlDep)
1089 // for now, don't put an instruction that does not have operand
1090 // interlocks in the delay slot of a branch
1091 if (! S.getInstrInfo().hasOperandInterlock(node->getOpCode()))
1094 // Finally, if the instruction preceeds the branch, we make sure the
1095 // instruction can be reordered relative to the branch. We simply check
1096 // if the instr. has only 1 outgoing edge, viz., a CD edge to the branch.
1098 if (nodeIsPredecessor)
1100 bool onlyCDEdgeToBranch = true;
1101 for (SchedGraphNode::const_iterator OEI = node->beginOutEdges();
1102 OEI != node->endOutEdges(); ++OEI)
1103 if (! (*OEI)->getSink()->isDummyNode()
1104 && ((*OEI)->getSink() != brNode
1105 || (*OEI)->getDepType() != SchedGraphEdge::CtrlDep))
1107 onlyCDEdgeToBranch = false;
1111 if (!onlyCDEdgeToBranch)
1120 MarkNodeForDelaySlot(SchedulingManager& S,
1122 SchedGraphNode* node,
1123 const SchedGraphNode* brNode,
1124 bool nodeIsPredecessor)
1126 if (nodeIsPredecessor)
1127 { // If node is in the same basic block (i.e., preceeds brNode),
1128 // remove it and all its incident edges from the graph. Make sure we
1129 // add dummy edges for pred/succ nodes that become entry/exit nodes.
1130 graph->eraseIncidentEdges(node, /*addDummyEdges*/ true);
1133 { // If the node was from a target block, add the node to the graph
1134 // and add a CD edge from brNode to node.
1135 assert(0 && "NOT IMPLEMENTED YET");
1138 DelaySlotInfo* dinfo = S.getDelaySlotInfoForInstr(brNode, /*create*/ true);
1139 dinfo->addDelayNode(node);
1144 FindUsefulInstructionsForDelaySlots(SchedulingManager& S,
1145 SchedGraphNode* brNode,
1146 vector<SchedGraphNode*>& sdelayNodeVec)
1148 const MachineInstrInfo& mii = S.getInstrInfo();
1150 mii.getNumDelaySlots(brNode->getOpCode());
1155 sdelayNodeVec.reserve(ndelays);
1157 // Use a separate vector to hold the feasible multi-cycle nodes.
1158 // These will be used if not enough single-cycle nodes are found.
1160 vector<SchedGraphNode*> mdelayNodeVec;
1162 for (sg_pred_iterator P = pred_begin(brNode);
1163 P != pred_end(brNode) && sdelayNodeVec.size() < ndelays; ++P)
1164 if (! (*P)->isDummyNode() &&
1165 ! mii.isNop((*P)->getOpCode()) &&
1166 NodeCanFillDelaySlot(S, *P, brNode, /*pred*/ true))
1168 if (mii.maxLatency((*P)->getOpCode()) > 1)
1169 mdelayNodeVec.push_back(*P);
1171 sdelayNodeVec.push_back(*P);
1174 // If not enough single-cycle instructions were found, select the
1175 // lowest-latency multi-cycle instructions and use them.
1176 // Note that this is the most efficient code when only 1 (or even 2)
1177 // values need to be selected.
1179 while (sdelayNodeVec.size() < ndelays && mdelayNodeVec.size() > 0)
1182 mii.maxLatency(mdelayNodeVec[0]->getOpCode());
1183 unsigned minIndex = 0;
1184 for (unsigned i=1; i < mdelayNodeVec.size(); i++)
1187 mii.maxLatency(mdelayNodeVec[i]->getOpCode());
1194 sdelayNodeVec.push_back(mdelayNodeVec[minIndex]);
1195 if (sdelayNodeVec.size() < ndelays) // avoid the last erase!
1196 mdelayNodeVec.erase(mdelayNodeVec.begin() + minIndex);
1201 // Remove the NOPs currently in delay slots from the graph.
1202 // Mark instructions specified in sdelayNodeVec to replace them.
1203 // If not enough useful instructions were found, mark the NOPs to be used
1204 // for filling delay slots, otherwise, otherwise just discard them.
1207 ReplaceNopsWithUsefulInstr(SchedulingManager& S,
1208 SchedGraphNode* node,
1209 vector<SchedGraphNode*> sdelayNodeVec,
1212 vector<SchedGraphNode*> nopNodeVec; // this will hold unused NOPs
1213 const MachineInstrInfo& mii = S.getInstrInfo();
1214 const MachineInstr* brInstr = node->getMachineInstr();
1215 unsigned ndelays= mii.getNumDelaySlots(brInstr->getOpCode());
1216 assert(ndelays > 0 && "Unnecessary call to replace NOPs");
1218 // Remove the NOPs currently in delay slots from the graph.
1219 // If not enough useful instructions were found, use the NOPs to
1220 // fill delay slots, otherwise, just discard them.
1222 unsigned int firstDelaySlotIdx = node->getOrigIndexInBB() + 1;
1223 MachineCodeForBasicBlock& bbMvec = node->getBB()->getMachineInstrVec();
1224 assert(bbMvec[firstDelaySlotIdx - 1] == brInstr &&
1225 "Incorrect instr. index in basic block for brInstr");
1227 // First find all useful instructions already in the delay slots
1228 // and USE THEM. We'll throw away the unused alternatives below
1230 for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
1231 if (! mii.isNop(bbMvec[i]->getOpCode()))
1232 sdelayNodeVec.insert(sdelayNodeVec.begin(),
1233 graph->getGraphNodeForInstr(bbMvec[i]));
1235 // Then find the NOPs and keep only as many as are needed.
1236 // Put the rest in nopNodeVec to be deleted.
1237 for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
1238 if (mii.isNop(bbMvec[i]->getOpCode()))
1239 if (sdelayNodeVec.size() < ndelays)
1240 sdelayNodeVec.push_back(graph->getGraphNodeForInstr(bbMvec[i]));
1242 nopNodeVec.push_back(graph->getGraphNodeForInstr(bbMvec[i]));
1244 assert(sdelayNodeVec.size() >= ndelays);
1246 // If some delay slots were already filled, throw away that many new choices
1247 if (sdelayNodeVec.size() > ndelays)
1248 sdelayNodeVec.resize(ndelays);
1250 // Mark the nodes chosen for delay slots. This removes them from the graph.
1251 for (unsigned i=0; i < sdelayNodeVec.size(); i++)
1252 MarkNodeForDelaySlot(S, graph, sdelayNodeVec[i], node, true);
1254 // And remove the unused NOPs from the graph.
1255 for (unsigned i=0; i < nopNodeVec.size(); i++)
1256 graph->eraseIncidentEdges(nopNodeVec[i], /*addDummyEdges*/ true);
1260 // For all delayed instructions, choose instructions to put in the delay
1261 // slots and pull those out of the graph. Mark them for the delay slots
1262 // in the DelaySlotInfo object for that graph node. If no useful work
1263 // is found for a delay slot, use the NOP that is currently in that slot.
1265 // We try to fill the delay slots with useful work for all instructions
1266 // EXCEPT CALLS AND RETURNS.
1267 // For CALLs and RETURNs, it is nearly always possible to use one of the
1268 // call sequence instrs and putting anything else in the delay slot could be
1269 // suboptimal. Also, it complicates generating the calling sequence code in
1273 ChooseInstructionsForDelaySlots(SchedulingManager& S,
1274 const BasicBlock *bb,
1277 const MachineInstrInfo& mii = S.getInstrInfo();
1278 const Instruction *termInstr = (Instruction*)bb->getTerminator();
1279 MachineCodeForInstruction &termMvec=MachineCodeForInstruction::get(termInstr);
1280 vector<SchedGraphNode*> delayNodeVec;
1281 const MachineInstr* brInstr = NULL;
1283 if (termInstr->getOpcode() != Instruction::Ret)
1285 // To find instructions that need delay slots without searching the full
1286 // machine code, we assume that the only delayed instructions are CALLs
1287 // or instructions generated for the terminator inst.
1288 // Find the first branch instr in the sequence of machine instrs for term
1291 while (first < termMvec.size() &&
1292 ! mii.isBranch(termMvec[first]->getOpCode()))
1296 assert(first < termMvec.size() &&
1297 "No branch instructions for BR? Ok, but weird! Delete assertion.");
1299 brInstr = (first < termMvec.size())? termMvec[first] : NULL;
1301 // Compute a vector of the nodes chosen for delay slots and then
1302 // mark delay slots to replace NOPs with these useful instructions.
1304 if (brInstr != NULL)
1306 SchedGraphNode* brNode = graph->getGraphNodeForInstr(brInstr);
1307 FindUsefulInstructionsForDelaySlots(S, brNode, delayNodeVec);
1308 ReplaceNopsWithUsefulInstr(S, brNode, delayNodeVec, graph);
1312 // Also mark delay slots for other delayed instructions to hold NOPs.
1313 // Simply passing in an empty delayNodeVec will have this effect.
1315 delayNodeVec.clear();
1316 const MachineCodeForBasicBlock& bbMvec = bb->getMachineInstrVec();
1317 for (unsigned i=0; i < bbMvec.size(); i++)
1318 if (bbMvec[i] != brInstr &&
1319 mii.getNumDelaySlots(bbMvec[i]->getOpCode()) > 0)
1321 SchedGraphNode* node = graph->getGraphNodeForInstr(bbMvec[i]);
1322 ReplaceNopsWithUsefulInstr(S, node, delayNodeVec, graph);
1328 // Schedule the delayed branch and its delay slots
1331 DelaySlotInfo::scheduleDelayedNode(SchedulingManager& S)
1333 assert(delayedNodeSlotNum < S.nslots && "Illegal slot for branch");
1334 assert(S.isched.getInstr(delayedNodeSlotNum, delayedNodeCycle) == NULL
1335 && "Slot for branch should be empty");
1337 unsigned int nextSlot = delayedNodeSlotNum;
1338 cycles_t nextTime = delayedNodeCycle;
1340 S.scheduleInstr(brNode, nextSlot, nextTime);
1342 for (unsigned d=0; d < ndelays; d++)
1345 if (nextSlot == S.nslots)
1351 // Find the first feasible instruction for this delay slot
1352 // Note that we only check for issue restrictions here.
1353 // We do *not* check for flow dependences but rely on pipeline
1354 // interlocks to resolve them. Machines without interlocks
1355 // will require this code to be modified.
1356 for (unsigned i=0; i < delayNodeVec.size(); i++)
1358 const SchedGraphNode* dnode = delayNodeVec[i];
1359 if ( ! S.isScheduled(dnode)
1360 && S.schedInfo.instrCanUseSlot(dnode->getOpCode(), nextSlot)
1361 && instrIsFeasible(S, dnode->getOpCode()))
1363 assert(S.getInstrInfo().hasOperandInterlock(dnode->getOpCode())
1364 && "Instructions without interlocks not yet supported "
1365 "when filling branch delay slots");
1366 S.scheduleInstr(dnode, nextSlot, nextTime);
1372 // Update current time if delay slots overflowed into later cycles.
1373 // Do this here because we know exactly which cycle is the last cycle
1374 // that contains delay slots. The next loop doesn't compute that.
1375 if (nextTime > S.getTime())
1376 S.updateTime(nextTime);
1378 // Now put any remaining instructions in the unfilled delay slots.
1379 // This could lead to suboptimal performance but needed for correctness.
1380 nextSlot = delayedNodeSlotNum;
1381 nextTime = delayedNodeCycle;
1382 for (unsigned i=0; i < delayNodeVec.size(); i++)
1383 if (! S.isScheduled(delayNodeVec[i]))
1385 do { // find the next empty slot
1387 if (nextSlot == S.nslots)
1392 } while (S.isched.getInstr(nextSlot, nextTime) != NULL);
1394 S.scheduleInstr(delayNodeVec[i], nextSlot, nextTime);
1402 // Check if the instruction would conflict with instructions already
1403 // chosen for the current cycle
1406 ConflictsWithChoices(const SchedulingManager& S,
1407 MachineOpCode opCode)
1409 // Check if the instruction must issue by itself, and some feasible
1410 // choices have already been made for this cycle
1411 if (S.getNumChoices() > 0 && S.schedInfo.isSingleIssue(opCode))
1414 // For each class that opCode belongs to, check if there are too many
1415 // instructions of that class.
1417 const InstrSchedClass sc = S.schedInfo.getSchedClass(opCode);
1418 return (S.getNumChoicesInClass(sc) == S.schedInfo.getMaxIssueForClass(sc));
1422 //************************* External Functions *****************************/
1425 //---------------------------------------------------------------------------
1426 // Function: ViolatesMinimumGap
1429 // Check minimum gap requirements relative to instructions scheduled in
1431 // Note that we do not need to consider `nextEarliestIssueTime' here because
1432 // that is also captured in the earliest start times for each opcode.
1433 //---------------------------------------------------------------------------
1436 ViolatesMinimumGap(const SchedulingManager& S,
1437 MachineOpCode opCode,
1438 const cycles_t inCycle)
1440 return (inCycle < S.getEarliestStartTimeForOp(opCode));
1444 //---------------------------------------------------------------------------
1445 // Function: instrIsFeasible
1448 // Check if any issue restrictions would prevent the instruction from
1449 // being issued in the current cycle
1450 //---------------------------------------------------------------------------
1453 instrIsFeasible(const SchedulingManager& S,
1454 MachineOpCode opCode)
1456 // skip the instruction if it cannot be issued due to issue restrictions
1457 // caused by previously issued instructions
1458 if (ViolatesMinimumGap(S, opCode, S.getTime()))
1461 // skip the instruction if it cannot be issued due to issue restrictions
1462 // caused by previously chosen instructions for the current cycle
1463 if (ConflictsWithChoices(S, opCode))
1469 //---------------------------------------------------------------------------
1470 // Function: ScheduleInstructionsWithSSA
1473 // Entry point for instruction scheduling on SSA form.
1474 // Schedules the machine instructions generated by instruction selection.
1475 // Assumes that register allocation has not been done, i.e., operands
1476 // are still in SSA form.
1477 //---------------------------------------------------------------------------
1480 class InstructionSchedulingWithSSA : public FunctionPass {
1481 const TargetMachine ⌖
1483 inline InstructionSchedulingWithSSA(const TargetMachine &T) : target(T) {}
1485 const char *getPassName() const { return "Instruction Scheduling"; }
1487 // getAnalysisUsage - We use LiveVarInfo...
1488 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1489 AU.addRequired(FunctionLiveVarInfo::ID);
1492 bool runOnFunction(Function *F);
1494 } // end anonymous namespace
1498 InstructionSchedulingWithSSA::runOnFunction(Function *M)
1500 if (SchedDebugLevel == Sched_Disable)
1503 SchedGraphSet graphSet(M, target);
1505 if (SchedDebugLevel >= Sched_PrintSchedGraphs)
1507 cerr << "\n*** SCHEDULING GRAPHS FOR INSTRUCTION SCHEDULING\n";
1511 for (SchedGraphSet::const_iterator GI=graphSet.begin(), GE=graphSet.end();
1514 SchedGraph* graph = (*GI);
1515 const vector<const BasicBlock*> &bbvec = graph->getBasicBlocks();
1516 assert(bbvec.size() == 1 && "Cannot schedule multiple basic blocks");
1517 const BasicBlock* bb = bbvec[0];
1519 if (SchedDebugLevel >= Sched_PrintSchedTrace)
1520 cerr << "\n*** TRACE OF INSTRUCTION SCHEDULING OPERATIONS\n\n";
1523 SchedPriorities schedPrio(M, graph,getAnalysis<FunctionLiveVarInfo>());
1524 SchedulingManager S(target, graph, schedPrio);
1526 ChooseInstructionsForDelaySlots(S, bb, graph); // modifies graph
1528 ForwardListSchedule(S); // computes schedule in S
1530 RecordSchedule(bb, S); // records schedule in BB
1533 if (SchedDebugLevel >= Sched_PrintMachineCode)
1535 cerr << "\n*** Machine instructions after INSTRUCTION SCHEDULING\n";
1536 MachineCodeForMethod::get(M).dump();
1543 Pass *createInstructionSchedulingWithSSAPass(const TargetMachine &tgt) {
1544 return new InstructionSchedulingWithSSA(tgt);