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/CodeGen/FunctionLiveVarInfo.h"
13 #include "llvm/Target/TargetMachine.h"
14 #include "llvm/BasicBlock.h"
15 #include "Support/CommandLine.h"
18 SchedDebugLevel_t SchedDebugLevel;
20 static cl::opt<bool> EnableFillingDelaySlots("sched-fill-delay-slots",
21 cl::desc("Fill branch delay slots during local scheduling"));
23 static cl::opt<SchedDebugLevel_t, true>
24 SDL_opt("dsched", cl::Hidden, cl::location(SchedDebugLevel),
25 cl::desc("enable instruction scheduling debugging information"),
27 clEnumValN(Sched_NoDebugInfo, "n", "disable debug output"),
28 clEnumValN(Sched_PrintMachineCode, "y", "print machine code after scheduling"),
29 clEnumValN(Sched_PrintSchedTrace, "t", "print trace of scheduling actions"),
30 clEnumValN(Sched_PrintSchedGraphs, "g", "print scheduling graphs"),
34 //************************* Internal Data Types *****************************/
37 class SchedulingManager;
40 //----------------------------------------------------------------------
43 // Represents a group of instructions scheduled to be issued
45 //----------------------------------------------------------------------
48 InstrGroup(const InstrGroup&); // DO NOT IMPLEMENT
49 void operator=(const InstrGroup&); // DO NOT IMPLEMENT
52 inline const SchedGraphNode* operator[](unsigned int slotNum) const {
53 assert(slotNum < group.size());
54 return group[slotNum];
58 friend class InstrSchedule;
60 inline void addInstr(const SchedGraphNode* node, unsigned int slotNum) {
61 assert(slotNum < group.size());
62 group[slotNum] = node;
65 /*ctor*/ InstrGroup(unsigned int nslots)
66 : group(nslots, NULL) {}
68 /*ctor*/ InstrGroup(); // disable: DO NOT IMPLEMENT
71 std::vector<const SchedGraphNode*> group;
75 //----------------------------------------------------------------------
76 // class ScheduleIterator:
78 // Iterates over the machine instructions in the for a single basic block.
79 // The schedule is represented by an InstrSchedule object.
80 //----------------------------------------------------------------------
82 template<class _NodeType>
83 class ScheduleIterator : public forward_iterator<_NodeType, ptrdiff_t> {
87 const InstrSchedule& S;
89 typedef ScheduleIterator<_NodeType> _Self;
91 /*ctor*/ inline ScheduleIterator(const InstrSchedule& _schedule,
94 : cycleNum(_cycleNum), slotNum(_slotNum), S(_schedule) {
98 /*ctor*/ inline ScheduleIterator(const _Self& x)
99 : cycleNum(x.cycleNum), slotNum(x.slotNum), S(x.S) {}
101 inline bool operator==(const _Self& x) const {
102 return (slotNum == x.slotNum && cycleNum== x.cycleNum && &S==&x.S);
105 inline bool operator!=(const _Self& x) const { return !operator==(x); }
107 inline _NodeType* operator*() const {
108 assert(cycleNum < S.groups.size());
109 return (*S.groups[cycleNum])[slotNum];
111 inline _NodeType* operator->() const { return operator*(); }
113 _Self& operator++(); // Preincrement
114 inline _Self operator++(int) { // Postincrement
115 _Self tmp(*this); ++*this; return tmp;
118 static _Self begin(const InstrSchedule& _schedule);
119 static _Self end( const InstrSchedule& _schedule);
122 inline _Self& operator=(const _Self& x); // DISABLE -- DO NOT IMPLEMENT
123 void skipToNextInstr();
127 //----------------------------------------------------------------------
128 // class InstrSchedule:
130 // Represents the schedule of machine instructions for a single basic block.
131 //----------------------------------------------------------------------
133 class InstrSchedule {
134 const unsigned int nslots;
135 unsigned int numInstr;
136 std::vector<InstrGroup*> groups; // indexed by cycle number
137 std::vector<cycles_t> startTime; // indexed by node id
139 InstrSchedule(InstrSchedule&); // DO NOT IMPLEMENT
140 void operator=(InstrSchedule&); // DO NOT IMPLEMENT
143 typedef ScheduleIterator<SchedGraphNode> iterator;
144 typedef ScheduleIterator<const SchedGraphNode> const_iterator;
147 const_iterator begin() const;
149 const_iterator end() const;
151 public: // constructors and destructor
152 /*ctor*/ InstrSchedule (unsigned int _nslots,
153 unsigned int _numNodes);
154 /*dtor*/ ~InstrSchedule ();
156 public: // accessor functions to query chosen schedule
157 const SchedGraphNode* getInstr (unsigned int slotNum,
159 const InstrGroup* igroup = this->getIGroup(c);
160 return (igroup == NULL)? NULL : (*igroup)[slotNum];
163 inline InstrGroup* getIGroup (cycles_t c) {
164 if ((unsigned)c >= groups.size())
166 if (groups[c] == NULL)
167 groups[c] = new InstrGroup(nslots);
171 inline const InstrGroup* getIGroup (cycles_t c) const {
172 assert((unsigned)c < groups.size());
176 inline cycles_t getStartTime (unsigned int nodeId) const {
177 assert(nodeId < startTime.size());
178 return startTime[nodeId];
181 unsigned int getNumInstructions() const {
185 inline void scheduleInstr (const SchedGraphNode* node,
186 unsigned int slotNum,
188 InstrGroup* igroup = this->getIGroup(cycle);
189 assert((*igroup)[slotNum] == NULL && "Slot already filled?");
190 igroup->addInstr(node, slotNum);
191 assert(node->getNodeId() < startTime.size());
192 startTime[node->getNodeId()] = cycle;
197 friend class iterator;
198 friend class const_iterator;
199 /*ctor*/ InstrSchedule (); // Disable: DO NOT IMPLEMENT.
204 InstrSchedule::InstrSchedule(unsigned int _nslots, unsigned int _numNodes)
207 groups(2 * _numNodes / _nslots), // 2 x lower-bound for #cycles
208 startTime(_numNodes, (cycles_t) -1) // set all to -1
214 InstrSchedule::~InstrSchedule()
216 for (unsigned c=0, NC=groups.size(); c < NC; c++)
217 if (groups[c] != NULL)
218 delete groups[c]; // delete InstrGroup objects
222 template<class _NodeType>
225 ScheduleIterator<_NodeType>::skipToNextInstr()
227 while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
228 ++cycleNum; // skip cycles with no instructions
230 while (cycleNum < S.groups.size() &&
231 (*S.groups[cycleNum])[slotNum] == NULL)
234 if (slotNum == S.nslots) {
237 while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
238 ++cycleNum; // skip cycles with no instructions
243 template<class _NodeType>
245 ScheduleIterator<_NodeType>&
246 ScheduleIterator<_NodeType>::operator++() // Preincrement
249 if (slotNum == S.nslots) {
257 template<class _NodeType>
258 ScheduleIterator<_NodeType>
259 ScheduleIterator<_NodeType>::begin(const InstrSchedule& _schedule)
261 return _Self(_schedule, 0, 0);
264 template<class _NodeType>
265 ScheduleIterator<_NodeType>
266 ScheduleIterator<_NodeType>::end(const InstrSchedule& _schedule)
268 return _Self(_schedule, _schedule.groups.size(), 0);
271 InstrSchedule::iterator
272 InstrSchedule::begin()
274 return iterator::begin(*this);
277 InstrSchedule::const_iterator
278 InstrSchedule::begin() const
280 return const_iterator::begin(*this);
283 InstrSchedule::iterator
286 return iterator::end(*this);
289 InstrSchedule::const_iterator
290 InstrSchedule::end() const
292 return const_iterator::end( *this);
296 //----------------------------------------------------------------------
297 // class DelaySlotInfo:
299 // Record information about delay slots for a single branch instruction.
300 // Delay slots are simply indexed by slot number 1 ... numDelaySlots
301 //----------------------------------------------------------------------
303 class DelaySlotInfo {
304 const SchedGraphNode* brNode;
306 std::vector<const SchedGraphNode*> delayNodeVec;
307 cycles_t delayedNodeCycle;
308 unsigned delayedNodeSlotNum;
310 DelaySlotInfo(const DelaySlotInfo &); // DO NOT IMPLEMENT
311 void operator=(const DelaySlotInfo&); // DO NOT IMPLEMENT
313 /*ctor*/ DelaySlotInfo (const SchedGraphNode* _brNode,
315 : brNode(_brNode), ndelays(_ndelays),
316 delayedNodeCycle(0), delayedNodeSlotNum(0) {}
318 inline unsigned getNumDelays () {
322 inline const std::vector<const SchedGraphNode*>& getDelayNodeVec() {
326 inline void addDelayNode (const SchedGraphNode* node) {
327 delayNodeVec.push_back(node);
328 assert(delayNodeVec.size() <= ndelays && "Too many delay slot instrs!");
331 inline void recordChosenSlot (cycles_t cycle, unsigned slotNum) {
332 delayedNodeCycle = cycle;
333 delayedNodeSlotNum = slotNum;
336 unsigned scheduleDelayedNode (SchedulingManager& S);
340 //----------------------------------------------------------------------
341 // class SchedulingManager:
343 // Represents the schedule of machine instructions for a single basic block.
344 //----------------------------------------------------------------------
346 class SchedulingManager {
347 SchedulingManager(SchedulingManager &); // DO NOT IMPLEMENT
348 void operator=(const SchedulingManager &); // DO NOT IMPLEMENT
349 public: // publicly accessible data members
350 const unsigned nslots;
351 const TargetSchedInfo& schedInfo;
352 SchedPriorities& schedPrio;
353 InstrSchedule isched;
356 unsigned totalInstrCount;
358 cycles_t nextEarliestIssueTime; // next cycle we can issue
360 std::vector<hash_set<const SchedGraphNode*> > choicesForSlot;
361 std::vector<const SchedGraphNode*> choiceVec; // indexed by node ptr
362 std::vector<int> numInClass; // indexed by sched class
363 std::vector<cycles_t> nextEarliestStartTime; // indexed by opCode
364 hash_map<const SchedGraphNode*, DelaySlotInfo*> delaySlotInfoForBranches;
365 // indexed by branch node ptr
368 SchedulingManager(const TargetMachine& _target, const SchedGraph* graph,
369 SchedPriorities& schedPrio);
370 ~SchedulingManager() {
371 for (hash_map<const SchedGraphNode*,
372 DelaySlotInfo*>::iterator I = delaySlotInfoForBranches.begin(),
373 E = delaySlotInfoForBranches.end(); I != E; ++I)
377 //----------------------------------------------------------------------
378 // Simplify access to the machine instruction info
379 //----------------------------------------------------------------------
381 inline const TargetInstrInfo& getInstrInfo () const {
382 return schedInfo.getInstrInfo();
385 //----------------------------------------------------------------------
386 // Interface for checking and updating the current time
387 //----------------------------------------------------------------------
389 inline cycles_t getTime () const {
393 inline cycles_t getEarliestIssueTime() const {
394 return nextEarliestIssueTime;
397 inline cycles_t getEarliestStartTimeForOp(MachineOpCode opCode) const {
398 assert(opCode < (int) nextEarliestStartTime.size());
399 return nextEarliestStartTime[opCode];
402 // Update current time to specified cycle
403 inline void updateTime (cycles_t c) {
405 schedPrio.updateTime(c);
408 //----------------------------------------------------------------------
409 // Functions to manage the choices for the current cycle including:
410 // -- a vector of choices by priority (choiceVec)
411 // -- vectors of the choices for each instruction slot (choicesForSlot[])
412 // -- number of choices in each sched class, used to check issue conflicts
413 // between choices for a single cycle
414 //----------------------------------------------------------------------
416 inline unsigned int getNumChoices () const {
417 return choiceVec.size();
420 inline unsigned getNumChoicesInClass (const InstrSchedClass& sc) const {
421 assert(sc < numInClass.size() && "Invalid op code or sched class!");
422 return numInClass[sc];
425 inline const SchedGraphNode* getChoice(unsigned int i) const {
426 // assert(i < choiceVec.size()); don't check here.
430 inline hash_set<const SchedGraphNode*>& getChoicesForSlot(unsigned slotNum) {
431 assert(slotNum < nslots);
432 return choicesForSlot[slotNum];
435 inline void addChoice (const SchedGraphNode* node) {
436 // Append the instruction to the vector of choices for current cycle.
437 // Increment numInClass[c] for the sched class to which the instr belongs.
438 choiceVec.push_back(node);
439 const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpCode());
440 assert(sc < numInClass.size());
444 inline void addChoiceToSlot (unsigned int slotNum,
445 const SchedGraphNode* node) {
446 // Add the instruction to the choice set for the specified slot
447 assert(slotNum < nslots);
448 choicesForSlot[slotNum].insert(node);
451 inline void resetChoices () {
453 for (unsigned int s=0; s < nslots; s++)
454 choicesForSlot[s].clear();
455 for (unsigned int c=0; c < numInClass.size(); c++)
459 //----------------------------------------------------------------------
460 // Code to query and manage the partial instruction schedule so far
461 //----------------------------------------------------------------------
463 inline unsigned int getNumScheduled () const {
464 return isched.getNumInstructions();
467 inline unsigned int getNumUnscheduled() const {
468 return totalInstrCount - isched.getNumInstructions();
471 inline bool isScheduled (const SchedGraphNode* node) const {
472 return (isched.getStartTime(node->getNodeId()) >= 0);
475 inline void scheduleInstr (const SchedGraphNode* node,
476 unsigned int slotNum,
479 assert(! isScheduled(node) && "Instruction already scheduled?");
481 // add the instruction to the schedule
482 isched.scheduleInstr(node, slotNum, cycle);
484 // update the earliest start times of all nodes that conflict with `node'
485 // and the next-earliest time anything can issue if `node' causes bubbles
486 updateEarliestStartTimes(node, cycle);
488 // remove the instruction from the choice sets for all slots
489 for (unsigned s=0; s < nslots; s++)
490 choicesForSlot[s].erase(node);
492 // and decrement the instr count for the sched class to which it belongs
493 const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpCode());
494 assert(sc < numInClass.size());
498 //----------------------------------------------------------------------
499 // Create and retrieve delay slot info for delayed instructions
500 //----------------------------------------------------------------------
502 inline DelaySlotInfo* getDelaySlotInfoForInstr(const SchedGraphNode* bn,
503 bool createIfMissing=false)
505 hash_map<const SchedGraphNode*, DelaySlotInfo*>::const_iterator
506 I = delaySlotInfoForBranches.find(bn);
507 if (I != delaySlotInfoForBranches.end())
510 if (!createIfMissing) return 0;
512 DelaySlotInfo *dinfo =
513 new DelaySlotInfo(bn, getInstrInfo().getNumDelaySlots(bn->getOpCode()));
514 return delaySlotInfoForBranches[bn] = dinfo;
518 SchedulingManager(); // DISABLED: DO NOT IMPLEMENT
519 void updateEarliestStartTimes(const SchedGraphNode* node, cycles_t schedTime);
524 SchedulingManager::SchedulingManager(const TargetMachine& target,
525 const SchedGraph* graph,
526 SchedPriorities& _schedPrio)
527 : nslots(target.getSchedInfo().getMaxNumIssueTotal()),
528 schedInfo(target.getSchedInfo()),
529 schedPrio(_schedPrio),
530 isched(nslots, graph->getNumNodes()),
531 totalInstrCount(graph->getNumNodes() - 2),
532 nextEarliestIssueTime(0),
533 choicesForSlot(nslots),
534 numInClass(target.getSchedInfo().getNumSchedClasses(), 0), // set all to 0
535 nextEarliestStartTime(target.getInstrInfo().getNumRealOpCodes(),
536 (cycles_t) 0) // set all to 0
540 // Note that an upper bound on #choices for each slot is = nslots since
541 // we use this vector to hold a feasible set of instructions, and more
542 // would be infeasible. Reserve that much memory since it is probably small.
543 for (unsigned int i=0; i < nslots; i++)
544 choicesForSlot[i].resize(nslots);
549 SchedulingManager::updateEarliestStartTimes(const SchedGraphNode* node,
552 if (schedInfo.numBubblesAfter(node->getOpCode()) > 0)
553 { // Update next earliest time before which *nothing* can issue.
554 nextEarliestIssueTime = std::max(nextEarliestIssueTime,
555 curTime + 1 + schedInfo.numBubblesAfter(node->getOpCode()));
558 const std::vector<MachineOpCode>&
559 conflictVec = schedInfo.getConflictList(node->getOpCode());
561 for (unsigned i=0; i < conflictVec.size(); i++)
563 MachineOpCode toOp = conflictVec[i];
564 cycles_t est=schedTime + schedInfo.getMinIssueGap(node->getOpCode(),toOp);
565 assert(toOp < (int) nextEarliestStartTime.size());
566 if (nextEarliestStartTime[toOp] < est)
567 nextEarliestStartTime[toOp] = est;
571 //************************* Internal Functions *****************************/
575 AssignInstructionsToSlots(class SchedulingManager& S, unsigned maxIssue)
577 // find the slot to start from, in the current cycle
578 unsigned int startSlot = 0;
579 cycles_t curTime = S.getTime();
581 assert(maxIssue > 0 && maxIssue <= S.nslots - startSlot);
583 // If only one instruction can be issued, do so.
585 for (unsigned s=startSlot; s < S.nslots; s++)
586 if (S.getChoicesForSlot(s).size() > 0) {
587 // found the one instruction
588 S.scheduleInstr(*S.getChoicesForSlot(s).begin(), s, curTime);
592 // Otherwise, choose from the choices for each slot
594 InstrGroup* igroup = S.isched.getIGroup(S.getTime());
595 assert(igroup != NULL && "Group creation failed?");
597 // Find a slot that has only a single choice, and take it.
598 // If all slots have 0 or multiple choices, pick the first slot with
599 // choices and use its last instruction (just to avoid shifting the vector).
601 for (numIssued = 0; numIssued < maxIssue; numIssued++) {
603 for (unsigned s=startSlot; s < S.nslots; s++)
604 if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() == 1) {
605 chosenSlot = (int) s;
609 if (chosenSlot == -1)
610 for (unsigned s=startSlot; s < S.nslots; s++)
611 if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() > 0) {
612 chosenSlot = (int) s;
616 if (chosenSlot != -1) {
617 // Insert the chosen instr in the chosen slot and
618 // erase it from all slots.
619 const SchedGraphNode* node= *S.getChoicesForSlot(chosenSlot).begin();
620 S.scheduleInstr(node, chosenSlot, curTime);
624 assert(numIssued > 0 && "Should not happen when maxIssue > 0!");
629 // For now, just assume we are scheduling within a single basic block.
630 // Get the machine instruction vector for the basic block and clear it,
631 // then append instructions in scheduled order.
632 // Also, re-insert the dummy PHI instructions that were at the beginning
633 // of the basic block, since they are not part of the schedule.
636 RecordSchedule(MachineBasicBlock &MBB, const SchedulingManager& S)
638 const TargetInstrInfo& mii = S.schedInfo.getInstrInfo();
641 // Lets make sure we didn't lose any instructions, except possibly
642 // some NOPs from delay slots. Also, PHIs are not included in the schedule.
643 unsigned numInstr = 0;
644 for (MachineBasicBlock::iterator I=MBB.begin(); I != MBB.end(); ++I)
645 if (! mii.isNop((*I)->getOpCode()) &&
646 ! mii.isDummyPhiInstr((*I)->getOpCode()))
648 assert(S.isched.getNumInstructions() >= numInstr &&
649 "Lost some non-NOP instructions during scheduling!");
652 if (S.isched.getNumInstructions() == 0)
653 return; // empty basic block!
655 // First find the dummy instructions at the start of the basic block
656 MachineBasicBlock::iterator I = MBB.begin();
657 for ( ; I != MBB.end(); ++I)
658 if (! mii.isDummyPhiInstr((*I)->getOpCode()))
661 // Erase all except the dummy PHI instructions from MBB, and
662 // pre-allocate create space for the ones we will put back in.
663 MBB.erase(I, MBB.end());
665 InstrSchedule::const_iterator NIend = S.isched.end();
666 for (InstrSchedule::const_iterator NI = S.isched.begin(); NI != NIend; ++NI)
667 MBB.push_back(const_cast<MachineInstr*>((*NI)->getMachineInstr()));
673 MarkSuccessorsReady(SchedulingManager& S, const SchedGraphNode* node)
675 // Check if any successors are now ready that were not already marked
676 // ready before, and that have not yet been scheduled.
678 for (sg_succ_const_iterator SI = succ_begin(node); SI !=succ_end(node); ++SI)
679 if (! (*SI)->isDummyNode()
680 && ! S.isScheduled(*SI)
681 && ! S.schedPrio.nodeIsReady(*SI))
683 // successor not scheduled and not marked ready; check *its* preds.
685 bool succIsReady = true;
686 for (sg_pred_const_iterator P=pred_begin(*SI); P != pred_end(*SI); ++P)
687 if (! (*P)->isDummyNode() && ! S.isScheduled(*P)) {
692 if (succIsReady) // add the successor to the ready list
693 S.schedPrio.insertReady(*SI);
698 // Choose up to `nslots' FEASIBLE instructions and assign each
699 // instruction to all possible slots that do not violate feasibility.
700 // FEASIBLE means it should be guaranteed that the set
701 // of chosen instructions can be issued in a single group.
704 // maxIssue : total number of feasible instructions
705 // S.choicesForSlot[i=0..nslots] : set of instructions feasible in slot i
708 FindSlotChoices(SchedulingManager& S,
709 DelaySlotInfo*& getDelaySlotInfo)
711 // initialize result vectors to empty
714 // find the slot to start from, in the current cycle
715 unsigned int startSlot = 0;
716 InstrGroup* igroup = S.isched.getIGroup(S.getTime());
717 for (int s = S.nslots - 1; s >= 0; s--)
718 if ((*igroup)[s] != NULL) {
723 // Make sure we pick at most one instruction that would break the group.
724 // Also, if we do pick one, remember which it was.
725 unsigned int indexForBreakingNode = S.nslots;
726 unsigned int indexForDelayedInstr = S.nslots;
727 DelaySlotInfo* delaySlotInfo = NULL;
729 getDelaySlotInfo = NULL;
731 // Choose instructions in order of priority.
732 // Add choices to the choice vector in the SchedulingManager class as
733 // we choose them so that subsequent choices will be correctly tested
734 // for feasibility, w.r.t. higher priority choices for the same cycle.
736 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) {
742 delaySlotInfo = S.getDelaySlotInfoForInstr(nextNode);
743 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();
751 } else if (S.schedInfo.breaksIssueGroup(nextNode->getOpCode())) {
752 if (indexForBreakingNode < S.nslots)
753 // have a breaking instruction already so throw this one away
756 indexForBreakingNode = S.getNumChoices();
759 if (nextNode != NULL) {
760 S.addChoice(nextNode);
762 if (S.schedInfo.isSingleIssue(nextNode->getOpCode())) {
763 assert(S.getNumChoices() == 1 &&
764 "Prioritizer returned invalid instr for this cycle!");
769 if (indexForDelayedInstr < S.nslots)
770 break; // leave the rest for delay slots
773 assert(S.getNumChoices() <= S.nslots);
774 assert(! (indexForDelayedInstr < S.nslots &&
775 indexForBreakingNode < S.nslots) && "Cannot have both in a cycle");
777 // Assign each chosen instruction to all possible slots for that instr.
778 // But if only one instruction was chosen, put it only in the first
779 // feasible slot; no more analysis will be needed.
781 if (indexForDelayedInstr >= S.nslots &&
782 indexForBreakingNode >= S.nslots)
783 { // No instructions that break the issue group or that have delay slots.
784 // This is the common case, so handle it separately for efficiency.
786 if (S.getNumChoices() == 1) {
787 MachineOpCode opCode = S.getChoice(0)->getOpCode();
789 for (s=startSlot; s < S.nslots; s++)
790 if (S.schedInfo.instrCanUseSlot(opCode, s))
792 assert(s < S.nslots && "No feasible slot for this opCode?");
793 S.addChoiceToSlot(s, S.getChoice(0));
795 for (unsigned i=0; i < S.getNumChoices(); i++) {
796 MachineOpCode opCode = S.getChoice(i)->getOpCode();
797 for (unsigned int s=startSlot; s < S.nslots; s++)
798 if (S.schedInfo.instrCanUseSlot(opCode, s))
799 S.addChoiceToSlot(s, S.getChoice(i));
802 } else if (indexForDelayedInstr < S.nslots) {
803 // There is an instruction that needs delay slots.
804 // Try to assign that instruction to a higher slot than any other
805 // instructions in the group, so that its delay slots can go
809 assert(indexForDelayedInstr == S.getNumChoices() - 1 &&
810 "Instruction with delay slots should be last choice!");
811 assert(delaySlotInfo != NULL && "No delay slot info for instr?");
813 const SchedGraphNode* delayedNode = S.getChoice(indexForDelayedInstr);
814 MachineOpCode delayOpCode = delayedNode->getOpCode();
815 unsigned ndelays= S.getInstrInfo().getNumDelaySlots(delayOpCode);
817 unsigned delayedNodeSlot = S.nslots;
820 // Find the last possible slot for the delayed instruction that leaves
821 // at least `d' slots vacant after it (d = #delay slots)
822 for (int s = S.nslots-ndelays-1; s >= (int) startSlot; s--)
823 if (S.schedInfo.instrCanUseSlot(delayOpCode, s)) {
828 highestSlotUsed = -1;
829 for (unsigned i=0; i < S.getNumChoices() - 1; i++) {
830 // Try to assign every other instruction to a lower numbered
831 // slot than delayedNodeSlot.
832 MachineOpCode opCode =S.getChoice(i)->getOpCode();
833 bool noSlotFound = true;
835 for (s=startSlot; s < delayedNodeSlot; s++)
836 if (S.schedInfo.instrCanUseSlot(opCode, s)) {
837 S.addChoiceToSlot(s, S.getChoice(i));
841 // No slot before `delayedNodeSlot' was found for this opCode
842 // Use a later slot, and allow some delay slots to fall in
845 for ( ; s < S.nslots; s++)
846 if (S.schedInfo.instrCanUseSlot(opCode, s)) {
847 S.addChoiceToSlot(s, S.getChoice(i));
851 assert(s < S.nslots && "No feasible slot for instruction?");
853 highestSlotUsed = std::max(highestSlotUsed, (int) s);
856 assert(highestSlotUsed <= (int) S.nslots-1 && "Invalid slot used?");
858 // We will put the delayed node in the first slot after the
859 // highest slot used. But we just mark that for now, and
860 // schedule it separately because we want to schedule the delay
861 // slots for the node at the same time.
862 cycles_t dcycle = S.getTime();
863 unsigned int dslot = highestSlotUsed + 1;
864 if (dslot == S.nslots) {
868 delaySlotInfo->recordChosenSlot(dcycle, dslot);
869 getDelaySlotInfo = delaySlotInfo;
871 // There is an instruction that breaks the issue group.
872 // For such an instruction, assign to the last possible slot in
873 // the current group, and then don't assign any other instructions
875 assert(indexForBreakingNode < S.nslots);
876 const SchedGraphNode* breakingNode=S.getChoice(indexForBreakingNode);
877 unsigned breakingSlot = INT_MAX;
878 unsigned int nslotsToUse = S.nslots;
880 // Find the last possible slot for this instruction.
881 for (int s = S.nslots-1; s >= (int) startSlot; s--)
882 if (S.schedInfo.instrCanUseSlot(breakingNode->getOpCode(), s)) {
886 assert(breakingSlot < S.nslots &&
887 "No feasible slot for `breakingNode'?");
889 // Higher priority instructions than the one that breaks the group:
890 // These can be assigned to all slots, but will be assigned only
891 // to earlier slots if possible.
893 i < S.getNumChoices() && i < indexForBreakingNode; i++)
895 MachineOpCode opCode =S.getChoice(i)->getOpCode();
897 // If a higher priority instruction cannot be assigned to
898 // any earlier slots, don't schedule the breaking instruction.
900 bool foundLowerSlot = false;
901 nslotsToUse = S.nslots; // May be modified in the loop
902 for (unsigned int s=startSlot; s < nslotsToUse; s++)
903 if (S.schedInfo.instrCanUseSlot(opCode, s)) {
904 if (breakingSlot < S.nslots && s < breakingSlot) {
905 foundLowerSlot = true;
906 nslotsToUse = breakingSlot; // RESETS LOOP UPPER BOUND!
909 S.addChoiceToSlot(s, S.getChoice(i));
913 breakingSlot = INT_MAX; // disable breaking instr
916 // Assign the breaking instruction (if any) to a single slot
917 // Otherwise, just ignore the instruction. It will simply be
918 // scheduled in a later cycle.
919 if (breakingSlot < S.nslots) {
920 S.addChoiceToSlot(breakingSlot, breakingNode);
921 nslotsToUse = breakingSlot;
923 nslotsToUse = S.nslots;
925 // For lower priority instructions than the one that breaks the
926 // group, only assign them to slots lower than the breaking slot.
927 // Otherwise, just ignore the instruction.
928 for (unsigned i=indexForBreakingNode+1; i < S.getNumChoices(); i++) {
929 MachineOpCode opCode = S.getChoice(i)->getOpCode();
930 for (unsigned int s=startSlot; s < nslotsToUse; s++)
931 if (S.schedInfo.instrCanUseSlot(opCode, s))
932 S.addChoiceToSlot(s, S.getChoice(i));
934 } // endif (no delay slots and no breaking slots)
936 return S.getNumChoices();
941 ChooseOneGroup(SchedulingManager& S)
943 assert(S.schedPrio.getNumReady() > 0
944 && "Don't get here without ready instructions.");
946 cycles_t firstCycle = S.getTime();
947 DelaySlotInfo* getDelaySlotInfo = NULL;
949 // Choose up to `nslots' feasible instructions and their possible slots.
950 unsigned numIssued = FindSlotChoices(S, getDelaySlotInfo);
952 while (numIssued == 0) {
953 S.updateTime(S.getTime()+1);
954 numIssued = FindSlotChoices(S, getDelaySlotInfo);
957 AssignInstructionsToSlots(S, numIssued);
959 if (getDelaySlotInfo != NULL)
960 numIssued += getDelaySlotInfo->scheduleDelayedNode(S);
962 // Print trace of scheduled instructions before newly ready ones
963 if (SchedDebugLevel >= Sched_PrintSchedTrace) {
964 for (cycles_t c = firstCycle; c <= S.getTime(); c++) {
965 std::cerr << " Cycle " << (long)c <<" : Scheduled instructions:\n";
966 const InstrGroup* igroup = S.isched.getIGroup(c);
967 for (unsigned int s=0; s < S.nslots; s++) {
969 if ((*igroup)[s] != NULL)
970 std::cerr << * ((*igroup)[s])->getMachineInstr() << "\n";
972 std::cerr << "<none>\n";
982 ForwardListSchedule(SchedulingManager& S)
985 const SchedGraphNode* node;
987 S.schedPrio.initialize();
989 while ((N = S.schedPrio.getNumReady()) > 0) {
990 cycles_t nextCycle = S.getTime();
992 // Choose one group of instructions for a cycle, plus any delay slot
993 // instructions (which may overflow into successive cycles).
994 // This will advance S.getTime() to the last cycle in which
995 // instructions are actually issued.
997 unsigned numIssued = ChooseOneGroup(S);
998 assert(numIssued > 0 && "Deadlock in list scheduling algorithm?");
1000 // Notify the priority manager of scheduled instructions and mark
1001 // any successors that may now be ready
1003 for (cycles_t c = nextCycle; c <= S.getTime(); c++) {
1004 const InstrGroup* igroup = S.isched.getIGroup(c);
1005 for (unsigned int s=0; s < S.nslots; s++)
1006 if ((node = (*igroup)[s]) != NULL) {
1007 S.schedPrio.issuedReadyNodeAt(S.getTime(), node);
1008 MarkSuccessorsReady(S, node);
1012 // Move to the next the next earliest cycle for which
1013 // an instruction can be issued, or the next earliest in which
1014 // one will be ready, or to the next cycle, whichever is latest.
1016 S.updateTime(std::max(S.getTime() + 1,
1017 std::max(S.getEarliestIssueTime(),
1018 S.schedPrio.getEarliestReadyTime())));
1023 //---------------------------------------------------------------------
1024 // Code for filling delay slots for delayed terminator instructions
1025 // (e.g., BRANCH and RETURN). Delay slots for non-terminator
1026 // instructions (e.g., CALL) are not handled here because they almost
1027 // always can be filled with instructions from the call sequence code
1028 // before a call. That's preferable because we incur many tradeoffs here
1029 // when we cannot find single-cycle instructions that can be reordered.
1030 //----------------------------------------------------------------------
1033 NodeCanFillDelaySlot(const SchedulingManager& S,
1034 const SchedGraphNode* node,
1035 const SchedGraphNode* brNode,
1036 bool nodeIsPredecessor)
1038 assert(! node->isDummyNode());
1040 // don't put a branch in the delay slot of another branch
1041 if (S.getInstrInfo().isBranch(node->getOpCode()))
1044 // don't put a single-issue instruction in the delay slot of a branch
1045 if (S.schedInfo.isSingleIssue(node->getOpCode()))
1048 // don't put a load-use dependence in the delay slot of a branch
1049 const TargetInstrInfo& mii = S.getInstrInfo();
1051 for (SchedGraphNode::const_iterator EI = node->beginInEdges();
1052 EI != node->endInEdges(); ++EI)
1053 if (! ((SchedGraphNode*)(*EI)->getSrc())->isDummyNode()
1054 && mii.isLoad(((SchedGraphNode*)(*EI)->getSrc())->getOpCode())
1055 && (*EI)->getDepType() == SchedGraphEdge::CtrlDep)
1058 // for now, don't put an instruction that does not have operand
1059 // interlocks in the delay slot of a branch
1060 if (! S.getInstrInfo().hasOperandInterlock(node->getOpCode()))
1063 // Finally, if the instruction precedes the branch, we make sure the
1064 // instruction can be reordered relative to the branch. We simply check
1065 // if the instr. has only 1 outgoing edge, viz., a CD edge to the branch.
1067 if (nodeIsPredecessor) {
1068 bool onlyCDEdgeToBranch = true;
1069 for (SchedGraphNode::const_iterator OEI = node->beginOutEdges();
1070 OEI != node->endOutEdges(); ++OEI)
1071 if (! ((SchedGraphNode*)(*OEI)->getSink())->isDummyNode()
1072 && ((*OEI)->getSink() != brNode
1073 || (*OEI)->getDepType() != SchedGraphEdge::CtrlDep))
1075 onlyCDEdgeToBranch = false;
1079 if (!onlyCDEdgeToBranch)
1088 MarkNodeForDelaySlot(SchedulingManager& S,
1090 SchedGraphNode* node,
1091 const SchedGraphNode* brNode,
1092 bool nodeIsPredecessor)
1094 if (nodeIsPredecessor) {
1095 // If node is in the same basic block (i.e., precedes brNode),
1096 // remove it and all its incident edges from the graph. Make sure we
1097 // add dummy edges for pred/succ nodes that become entry/exit nodes.
1098 graph->eraseIncidentEdges(node, /*addDummyEdges*/ true);
1100 // If the node was from a target block, add the node to the graph
1101 // and add a CD edge from brNode to node.
1102 assert(0 && "NOT IMPLEMENTED YET");
1105 DelaySlotInfo* dinfo = S.getDelaySlotInfoForInstr(brNode, /*create*/ true);
1106 dinfo->addDelayNode(node);
1111 FindUsefulInstructionsForDelaySlots(SchedulingManager& S,
1112 SchedGraphNode* brNode,
1113 std::vector<SchedGraphNode*>& sdelayNodeVec)
1115 const TargetInstrInfo& mii = S.getInstrInfo();
1117 mii.getNumDelaySlots(brNode->getOpCode());
1122 sdelayNodeVec.reserve(ndelays);
1124 // Use a separate vector to hold the feasible multi-cycle nodes.
1125 // These will be used if not enough single-cycle nodes are found.
1127 std::vector<SchedGraphNode*> mdelayNodeVec;
1129 for (sg_pred_iterator P = pred_begin(brNode);
1130 P != pred_end(brNode) && sdelayNodeVec.size() < ndelays; ++P)
1131 if (! (*P)->isDummyNode() &&
1132 ! mii.isNop((*P)->getOpCode()) &&
1133 NodeCanFillDelaySlot(S, *P, brNode, /*pred*/ true))
1135 if (mii.maxLatency((*P)->getOpCode()) > 1)
1136 mdelayNodeVec.push_back(*P);
1138 sdelayNodeVec.push_back(*P);
1141 // If not enough single-cycle instructions were found, select the
1142 // lowest-latency multi-cycle instructions and use them.
1143 // Note that this is the most efficient code when only 1 (or even 2)
1144 // values need to be selected.
1146 while (sdelayNodeVec.size() < ndelays && mdelayNodeVec.size() > 0) {
1148 mii.maxLatency(mdelayNodeVec[0]->getOpCode());
1149 unsigned minIndex = 0;
1150 for (unsigned i=1; i < mdelayNodeVec.size(); i++)
1153 mii.maxLatency(mdelayNodeVec[i]->getOpCode());
1160 sdelayNodeVec.push_back(mdelayNodeVec[minIndex]);
1161 if (sdelayNodeVec.size() < ndelays) // avoid the last erase!
1162 mdelayNodeVec.erase(mdelayNodeVec.begin() + minIndex);
1167 // Remove the NOPs currently in delay slots from the graph.
1168 // Mark instructions specified in sdelayNodeVec to replace them.
1169 // If not enough useful instructions were found, mark the NOPs to be used
1170 // for filling delay slots, otherwise, otherwise just discard them.
1172 static void ReplaceNopsWithUsefulInstr(SchedulingManager& S,
1173 SchedGraphNode* node,
1174 // FIXME: passing vector BY VALUE!!!
1175 std::vector<SchedGraphNode*> sdelayNodeVec,
1178 std::vector<SchedGraphNode*> nopNodeVec; // this will hold unused NOPs
1179 const TargetInstrInfo& mii = S.getInstrInfo();
1180 const MachineInstr* brInstr = node->getMachineInstr();
1181 unsigned ndelays= mii.getNumDelaySlots(brInstr->getOpCode());
1182 assert(ndelays > 0 && "Unnecessary call to replace NOPs");
1184 // Remove the NOPs currently in delay slots from the graph.
1185 // If not enough useful instructions were found, use the NOPs to
1186 // fill delay slots, otherwise, just discard them.
1188 unsigned int firstDelaySlotIdx = node->getOrigIndexInBB() + 1;
1189 MachineBasicBlock& MBB = node->getMachineBasicBlock();
1190 assert(MBB[firstDelaySlotIdx - 1] == brInstr &&
1191 "Incorrect instr. index in basic block for brInstr");
1193 // First find all useful instructions already in the delay slots
1194 // and USE THEM. We'll throw away the unused alternatives below
1196 for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
1197 if (! mii.isNop(MBB[i]->getOpCode()))
1198 sdelayNodeVec.insert(sdelayNodeVec.begin(),
1199 graph->getGraphNodeForInstr(MBB[i]));
1201 // Then find the NOPs and keep only as many as are needed.
1202 // Put the rest in nopNodeVec to be deleted.
1203 for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
1204 if (mii.isNop(MBB[i]->getOpCode()))
1205 if (sdelayNodeVec.size() < ndelays)
1206 sdelayNodeVec.push_back(graph->getGraphNodeForInstr(MBB[i]));
1208 nopNodeVec.push_back(graph->getGraphNodeForInstr(MBB[i]));
1210 //remove the MI from the Machine Code For Instruction
1211 const TerminatorInst *TI = MBB.getBasicBlock()->getTerminator();
1212 MachineCodeForInstruction& llvmMvec =
1213 MachineCodeForInstruction::get((const Instruction *)TI);
1215 for(MachineCodeForInstruction::iterator mciI=llvmMvec.begin(),
1216 mciE=llvmMvec.end(); mciI!=mciE; ++mciI){
1218 llvmMvec.erase(mciI);
1222 assert(sdelayNodeVec.size() >= ndelays);
1224 // If some delay slots were already filled, throw away that many new choices
1225 if (sdelayNodeVec.size() > ndelays)
1226 sdelayNodeVec.resize(ndelays);
1228 // Mark the nodes chosen for delay slots. This removes them from the graph.
1229 for (unsigned i=0; i < sdelayNodeVec.size(); i++)
1230 MarkNodeForDelaySlot(S, graph, sdelayNodeVec[i], node, true);
1232 // And remove the unused NOPs from the graph.
1233 for (unsigned i=0; i < nopNodeVec.size(); i++)
1234 graph->eraseIncidentEdges(nopNodeVec[i], /*addDummyEdges*/ true);
1238 // For all delayed instructions, choose instructions to put in the delay
1239 // slots and pull those out of the graph. Mark them for the delay slots
1240 // in the DelaySlotInfo object for that graph node. If no useful work
1241 // is found for a delay slot, use the NOP that is currently in that slot.
1243 // We try to fill the delay slots with useful work for all instructions
1244 // EXCEPT CALLS AND RETURNS.
1245 // For CALLs and RETURNs, it is nearly always possible to use one of the
1246 // call sequence instrs and putting anything else in the delay slot could be
1247 // suboptimal. Also, it complicates generating the calling sequence code in
1251 ChooseInstructionsForDelaySlots(SchedulingManager& S, MachineBasicBlock &MBB,
1254 const TargetInstrInfo& mii = S.getInstrInfo();
1256 Instruction *termInstr = (Instruction*)MBB.getBasicBlock()->getTerminator();
1257 MachineCodeForInstruction &termMvec=MachineCodeForInstruction::get(termInstr);
1258 std::vector<SchedGraphNode*> delayNodeVec;
1259 const MachineInstr* brInstr = NULL;
1261 if (EnableFillingDelaySlots &&
1262 termInstr->getOpcode() != Instruction::Ret)
1264 // To find instructions that need delay slots without searching the full
1265 // machine code, we assume that the only delayed instructions are CALLs
1266 // or instructions generated for the terminator inst.
1267 // Find the first branch instr in the sequence of machine instrs for term
1270 while (first < termMvec.size() &&
1271 ! mii.isBranch(termMvec[first]->getOpCode()))
1275 assert(first < termMvec.size() &&
1276 "No branch instructions for BR? Ok, but weird! Delete assertion.");
1278 brInstr = (first < termMvec.size())? termMvec[first] : NULL;
1280 // Compute a vector of the nodes chosen for delay slots and then
1281 // mark delay slots to replace NOPs with these useful instructions.
1283 if (brInstr != NULL) {
1284 SchedGraphNode* brNode = graph->getGraphNodeForInstr(brInstr);
1285 FindUsefulInstructionsForDelaySlots(S, brNode, delayNodeVec);
1286 ReplaceNopsWithUsefulInstr(S, brNode, delayNodeVec, graph);
1290 // Also mark delay slots for other delayed instructions to hold NOPs.
1291 // Simply passing in an empty delayNodeVec will have this effect.
1292 // If brInstr is not handled above (EnableFillingDelaySlots == false),
1293 // brInstr will be NULL so this will handle the branch instrs. as well.
1295 delayNodeVec.clear();
1296 for (unsigned i=0; i < MBB.size(); ++i)
1297 if (MBB[i] != brInstr &&
1298 mii.getNumDelaySlots(MBB[i]->getOpCode()) > 0)
1300 SchedGraphNode* node = graph->getGraphNodeForInstr(MBB[i]);
1301 ReplaceNopsWithUsefulInstr(S, node, delayNodeVec, graph);
1307 // Schedule the delayed branch and its delay slots
1310 DelaySlotInfo::scheduleDelayedNode(SchedulingManager& S)
1312 assert(delayedNodeSlotNum < S.nslots && "Illegal slot for branch");
1313 assert(S.isched.getInstr(delayedNodeSlotNum, delayedNodeCycle) == NULL
1314 && "Slot for branch should be empty");
1316 unsigned int nextSlot = delayedNodeSlotNum;
1317 cycles_t nextTime = delayedNodeCycle;
1319 S.scheduleInstr(brNode, nextSlot, nextTime);
1321 for (unsigned d=0; d < ndelays; d++) {
1323 if (nextSlot == S.nslots) {
1328 // Find the first feasible instruction for this delay slot
1329 // Note that we only check for issue restrictions here.
1330 // We do *not* check for flow dependences but rely on pipeline
1331 // interlocks to resolve them. Machines without interlocks
1332 // will require this code to be modified.
1333 for (unsigned i=0; i < delayNodeVec.size(); i++) {
1334 const SchedGraphNode* dnode = delayNodeVec[i];
1335 if ( ! S.isScheduled(dnode)
1336 && S.schedInfo.instrCanUseSlot(dnode->getOpCode(), nextSlot)
1337 && instrIsFeasible(S, dnode->getOpCode()))
1339 assert(S.getInstrInfo().hasOperandInterlock(dnode->getOpCode())
1340 && "Instructions without interlocks not yet supported "
1341 "when filling branch delay slots");
1342 S.scheduleInstr(dnode, nextSlot, nextTime);
1348 // Update current time if delay slots overflowed into later cycles.
1349 // Do this here because we know exactly which cycle is the last cycle
1350 // that contains delay slots. The next loop doesn't compute that.
1351 if (nextTime > S.getTime())
1352 S.updateTime(nextTime);
1354 // Now put any remaining instructions in the unfilled delay slots.
1355 // This could lead to suboptimal performance but needed for correctness.
1356 nextSlot = delayedNodeSlotNum;
1357 nextTime = delayedNodeCycle;
1358 for (unsigned i=0; i < delayNodeVec.size(); i++)
1359 if (! S.isScheduled(delayNodeVec[i])) {
1360 do { // find the next empty slot
1362 if (nextSlot == S.nslots) {
1366 } while (S.isched.getInstr(nextSlot, nextTime) != NULL);
1368 S.scheduleInstr(delayNodeVec[i], nextSlot, nextTime);
1376 // Check if the instruction would conflict with instructions already
1377 // chosen for the current cycle
1380 ConflictsWithChoices(const SchedulingManager& S,
1381 MachineOpCode opCode)
1383 // Check if the instruction must issue by itself, and some feasible
1384 // choices have already been made for this cycle
1385 if (S.getNumChoices() > 0 && S.schedInfo.isSingleIssue(opCode))
1388 // For each class that opCode belongs to, check if there are too many
1389 // instructions of that class.
1391 const InstrSchedClass sc = S.schedInfo.getSchedClass(opCode);
1392 return (S.getNumChoicesInClass(sc) == S.schedInfo.getMaxIssueForClass(sc));
1396 //************************* External Functions *****************************/
1399 //---------------------------------------------------------------------------
1400 // Function: ViolatesMinimumGap
1403 // Check minimum gap requirements relative to instructions scheduled in
1405 // Note that we do not need to consider `nextEarliestIssueTime' here because
1406 // that is also captured in the earliest start times for each opcode.
1407 //---------------------------------------------------------------------------
1410 ViolatesMinimumGap(const SchedulingManager& S,
1411 MachineOpCode opCode,
1412 const cycles_t inCycle)
1414 return (inCycle < S.getEarliestStartTimeForOp(opCode));
1418 //---------------------------------------------------------------------------
1419 // Function: instrIsFeasible
1422 // Check if any issue restrictions would prevent the instruction from
1423 // being issued in the current cycle
1424 //---------------------------------------------------------------------------
1427 instrIsFeasible(const SchedulingManager& S,
1428 MachineOpCode opCode)
1430 // skip the instruction if it cannot be issued due to issue restrictions
1431 // caused by previously issued instructions
1432 if (ViolatesMinimumGap(S, opCode, S.getTime()))
1435 // skip the instruction if it cannot be issued due to issue restrictions
1436 // caused by previously chosen instructions for the current cycle
1437 if (ConflictsWithChoices(S, opCode))
1443 //---------------------------------------------------------------------------
1444 // Function: ScheduleInstructionsWithSSA
1447 // Entry point for instruction scheduling on SSA form.
1448 // Schedules the machine instructions generated by instruction selection.
1449 // Assumes that register allocation has not been done, i.e., operands
1450 // are still in SSA form.
1451 //---------------------------------------------------------------------------
1454 class InstructionSchedulingWithSSA : public FunctionPass {
1455 const TargetMachine ⌖
1457 inline InstructionSchedulingWithSSA(const TargetMachine &T) : target(T) {}
1459 const char *getPassName() const { return "Instruction Scheduling"; }
1461 // getAnalysisUsage - We use LiveVarInfo...
1462 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1463 AU.addRequired<FunctionLiveVarInfo>();
1464 AU.setPreservesCFG();
1467 bool runOnFunction(Function &F);
1469 } // end anonymous namespace
1472 bool InstructionSchedulingWithSSA::runOnFunction(Function &F)
1474 SchedGraphSet graphSet(&F, target);
1476 if (SchedDebugLevel >= Sched_PrintSchedGraphs) {
1477 std::cerr << "\n*** SCHEDULING GRAPHS FOR INSTRUCTION SCHEDULING\n";
1481 for (SchedGraphSet::const_iterator GI=graphSet.begin(), GE=graphSet.end();
1484 SchedGraph* graph = (*GI);
1485 MachineBasicBlock &MBB = graph->getBasicBlock();
1487 if (SchedDebugLevel >= Sched_PrintSchedTrace)
1488 std::cerr << "\n*** TRACE OF INSTRUCTION SCHEDULING OPERATIONS\n\n";
1491 SchedPriorities schedPrio(&F, graph, getAnalysis<FunctionLiveVarInfo>());
1492 SchedulingManager S(target, graph, schedPrio);
1494 ChooseInstructionsForDelaySlots(S, MBB, graph); // modifies graph
1495 ForwardListSchedule(S); // computes schedule in S
1496 RecordSchedule(MBB, S); // records schedule in BB
1499 if (SchedDebugLevel >= Sched_PrintMachineCode) {
1500 std::cerr << "\n*** Machine instructions after INSTRUCTION SCHEDULING\n";
1501 MachineFunction::get(&F).dump();
1508 FunctionPass *createInstructionSchedulingWithSSAPass(const TargetMachine &tgt) {
1509 return new InstructionSchedulingWithSSA(tgt);