1 //===- InstrScheduling.cpp - Generic Instruction Scheduling support -------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the llvm/CodeGen/InstrScheduling.h interface, along with
11 // generic support routines for instruction scheduling.
13 //===----------------------------------------------------------------------===//
15 #include "SchedPriorities.h"
16 #include "llvm/CodeGen/MachineInstr.h"
17 #include "llvm/CodeGen/MachineCodeForInstruction.h"
18 #include "llvm/CodeGen/MachineFunction.h"
19 #include "../../Target/SparcV9/LiveVar/FunctionLiveVarInfo.h"
20 #include "llvm/Target/TargetMachine.h"
21 #include "llvm/BasicBlock.h"
22 #include "Support/CommandLine.h"
27 SchedDebugLevel_t SchedDebugLevel;
29 static cl::opt<bool> EnableFillingDelaySlots("sched-fill-delay-slots",
30 cl::desc("Fill branch delay slots during local scheduling"));
32 static cl::opt<SchedDebugLevel_t, true>
33 SDL_opt("dsched", cl::Hidden, cl::location(SchedDebugLevel),
34 cl::desc("enable instruction scheduling debugging information"),
36 clEnumValN(Sched_NoDebugInfo, "n", "disable debug output"),
37 clEnumValN(Sched_PrintMachineCode, "y", "print machine code after scheduling"),
38 clEnumValN(Sched_PrintSchedTrace, "t", "print trace of scheduling actions"),
39 clEnumValN(Sched_PrintSchedGraphs, "g", "print scheduling graphs"),
43 //************************* Internal Data Types *****************************/
46 class SchedulingManager;
49 //----------------------------------------------------------------------
52 // Represents a group of instructions scheduled to be issued
54 //----------------------------------------------------------------------
57 InstrGroup(const InstrGroup&); // DO NOT IMPLEMENT
58 void operator=(const InstrGroup&); // DO NOT IMPLEMENT
61 inline const SchedGraphNode* operator[](unsigned int slotNum) const {
62 assert(slotNum < group.size());
63 return group[slotNum];
67 friend class InstrSchedule;
69 inline void addInstr(const SchedGraphNode* node, unsigned int slotNum) {
70 assert(slotNum < group.size());
71 group[slotNum] = node;
74 /*ctor*/ InstrGroup(unsigned int nslots)
75 : group(nslots, NULL) {}
77 /*ctor*/ InstrGroup(); // disable: DO NOT IMPLEMENT
80 std::vector<const SchedGraphNode*> group;
84 //----------------------------------------------------------------------
85 // class ScheduleIterator:
87 // Iterates over the machine instructions in the for a single basic block.
88 // The schedule is represented by an InstrSchedule object.
89 //----------------------------------------------------------------------
91 template<class _NodeType>
92 class ScheduleIterator : public forward_iterator<_NodeType, ptrdiff_t> {
96 const InstrSchedule& S;
98 typedef ScheduleIterator<_NodeType> _Self;
100 /*ctor*/ inline ScheduleIterator(const InstrSchedule& _schedule,
103 : cycleNum(_cycleNum), slotNum(_slotNum), S(_schedule) {
107 /*ctor*/ inline ScheduleIterator(const _Self& x)
108 : cycleNum(x.cycleNum), slotNum(x.slotNum), S(x.S) {}
110 inline bool operator==(const _Self& x) const {
111 return (slotNum == x.slotNum && cycleNum== x.cycleNum && &S==&x.S);
114 inline bool operator!=(const _Self& x) const { return !operator==(x); }
116 inline _NodeType* operator*() const;
117 inline _NodeType* operator->() const { return operator*(); }
119 _Self& operator++(); // Preincrement
120 inline _Self operator++(int) { // Postincrement
121 _Self tmp(*this); ++*this; return tmp;
124 static _Self begin(const InstrSchedule& _schedule);
125 static _Self end( const InstrSchedule& _schedule);
128 inline _Self& operator=(const _Self& x); // DISABLE -- DO NOT IMPLEMENT
129 void skipToNextInstr();
133 //----------------------------------------------------------------------
134 // class InstrSchedule:
136 // Represents the schedule of machine instructions for a single basic block.
137 //----------------------------------------------------------------------
139 class InstrSchedule {
140 const unsigned int nslots;
141 unsigned int numInstr;
142 std::vector<InstrGroup*> groups; // indexed by cycle number
143 std::vector<cycles_t> startTime; // indexed by node id
145 InstrSchedule(InstrSchedule&); // DO NOT IMPLEMENT
146 void operator=(InstrSchedule&); // DO NOT IMPLEMENT
149 typedef ScheduleIterator<SchedGraphNode> iterator;
150 typedef ScheduleIterator<const SchedGraphNode> const_iterator;
152 iterator begin() { return iterator::begin(*this); }
153 const_iterator begin() const { return const_iterator::begin(*this); }
154 iterator end() { return iterator::end(*this); }
155 const_iterator end() const { return const_iterator::end(*this); }
157 public: // constructors and destructor
158 /*ctor*/ InstrSchedule (unsigned int _nslots,
159 unsigned int _numNodes);
160 /*dtor*/ ~InstrSchedule ();
162 public: // accessor functions to query chosen schedule
163 const SchedGraphNode* getInstr (unsigned int slotNum,
165 const InstrGroup* igroup = this->getIGroup(c);
166 return (igroup == NULL)? NULL : (*igroup)[slotNum];
169 inline InstrGroup* getIGroup (cycles_t c) {
170 if ((unsigned)c >= groups.size())
172 if (groups[c] == NULL)
173 groups[c] = new InstrGroup(nslots);
177 inline const InstrGroup* getIGroup (cycles_t c) const {
178 assert((unsigned)c < groups.size());
182 inline cycles_t getStartTime (unsigned int nodeId) const {
183 assert(nodeId < startTime.size());
184 return startTime[nodeId];
187 unsigned int getNumInstructions() const {
191 inline void scheduleInstr (const SchedGraphNode* node,
192 unsigned int slotNum,
194 InstrGroup* igroup = this->getIGroup(cycle);
195 assert((*igroup)[slotNum] == NULL && "Slot already filled?");
196 igroup->addInstr(node, slotNum);
197 assert(node->getNodeId() < startTime.size());
198 startTime[node->getNodeId()] = cycle;
203 friend class ScheduleIterator<SchedGraphNode>;
204 friend class ScheduleIterator<const SchedGraphNode>;
205 /*ctor*/ InstrSchedule (); // Disable: DO NOT IMPLEMENT.
208 template<class NodeType>
209 inline NodeType *ScheduleIterator<NodeType>::operator*() const {
210 assert(cycleNum < S.groups.size());
211 return (*S.groups[cycleNum])[slotNum];
216 InstrSchedule::InstrSchedule(unsigned int _nslots, unsigned int _numNodes)
219 groups(2 * _numNodes / _nslots), // 2 x lower-bound for #cycles
220 startTime(_numNodes, (cycles_t) -1) // set all to -1
226 InstrSchedule::~InstrSchedule()
228 for (unsigned c=0, NC=groups.size(); c < NC; c++)
229 if (groups[c] != NULL)
230 delete groups[c]; // delete InstrGroup objects
234 template<class _NodeType>
237 ScheduleIterator<_NodeType>::skipToNextInstr()
239 while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
240 ++cycleNum; // skip cycles with no instructions
242 while (cycleNum < S.groups.size() &&
243 (*S.groups[cycleNum])[slotNum] == NULL)
246 if (slotNum == S.nslots) {
249 while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
250 ++cycleNum; // skip cycles with no instructions
255 template<class _NodeType>
257 ScheduleIterator<_NodeType>&
258 ScheduleIterator<_NodeType>::operator++() // Preincrement
261 if (slotNum == S.nslots) {
269 template<class _NodeType>
270 ScheduleIterator<_NodeType>
271 ScheduleIterator<_NodeType>::begin(const InstrSchedule& _schedule)
273 return _Self(_schedule, 0, 0);
276 template<class _NodeType>
277 ScheduleIterator<_NodeType>
278 ScheduleIterator<_NodeType>::end(const InstrSchedule& _schedule)
280 return _Self(_schedule, _schedule.groups.size(), 0);
284 //----------------------------------------------------------------------
285 // class DelaySlotInfo:
287 // Record information about delay slots for a single branch instruction.
288 // Delay slots are simply indexed by slot number 1 ... numDelaySlots
289 //----------------------------------------------------------------------
291 class DelaySlotInfo {
292 const SchedGraphNode* brNode;
294 std::vector<const SchedGraphNode*> delayNodeVec;
295 cycles_t delayedNodeCycle;
296 unsigned delayedNodeSlotNum;
298 DelaySlotInfo(const DelaySlotInfo &); // DO NOT IMPLEMENT
299 void operator=(const DelaySlotInfo&); // DO NOT IMPLEMENT
301 /*ctor*/ DelaySlotInfo (const SchedGraphNode* _brNode,
303 : brNode(_brNode), ndelays(_ndelays),
304 delayedNodeCycle(0), delayedNodeSlotNum(0) {}
306 inline unsigned getNumDelays () {
310 inline const std::vector<const SchedGraphNode*>& getDelayNodeVec() {
314 inline void addDelayNode (const SchedGraphNode* node) {
315 delayNodeVec.push_back(node);
316 assert(delayNodeVec.size() <= ndelays && "Too many delay slot instrs!");
319 inline void recordChosenSlot (cycles_t cycle, unsigned slotNum) {
320 delayedNodeCycle = cycle;
321 delayedNodeSlotNum = slotNum;
324 unsigned scheduleDelayedNode (SchedulingManager& S);
328 //----------------------------------------------------------------------
329 // class SchedulingManager:
331 // Represents the schedule of machine instructions for a single basic block.
332 //----------------------------------------------------------------------
334 class SchedulingManager {
335 SchedulingManager(SchedulingManager &); // DO NOT IMPLEMENT
336 void operator=(const SchedulingManager &); // DO NOT IMPLEMENT
337 public: // publicly accessible data members
338 const unsigned nslots;
339 const TargetSchedInfo& schedInfo;
340 SchedPriorities& schedPrio;
341 InstrSchedule isched;
344 unsigned totalInstrCount;
346 cycles_t nextEarliestIssueTime; // next cycle we can issue
348 std::vector<hash_set<const SchedGraphNode*> > choicesForSlot;
349 std::vector<const SchedGraphNode*> choiceVec; // indexed by node ptr
350 std::vector<int> numInClass; // indexed by sched class
351 std::vector<cycles_t> nextEarliestStartTime; // indexed by opCode
352 hash_map<const SchedGraphNode*, DelaySlotInfo*> delaySlotInfoForBranches;
353 // indexed by branch node ptr
356 SchedulingManager(const TargetMachine& _target, const SchedGraph* graph,
357 SchedPriorities& schedPrio);
358 ~SchedulingManager() {
359 for (hash_map<const SchedGraphNode*,
360 DelaySlotInfo*>::iterator I = delaySlotInfoForBranches.begin(),
361 E = delaySlotInfoForBranches.end(); I != E; ++I)
365 //----------------------------------------------------------------------
366 // Simplify access to the machine instruction info
367 //----------------------------------------------------------------------
369 inline const TargetInstrInfo& getInstrInfo () const {
370 return schedInfo.getInstrInfo();
373 //----------------------------------------------------------------------
374 // Interface for checking and updating the current time
375 //----------------------------------------------------------------------
377 inline cycles_t getTime () const {
381 inline cycles_t getEarliestIssueTime() const {
382 return nextEarliestIssueTime;
385 inline cycles_t getEarliestStartTimeForOp(MachineOpCode opCode) const {
386 assert(opCode < (int) nextEarliestStartTime.size());
387 return nextEarliestStartTime[opCode];
390 // Update current time to specified cycle
391 inline void updateTime (cycles_t c) {
393 schedPrio.updateTime(c);
396 //----------------------------------------------------------------------
397 // Functions to manage the choices for the current cycle including:
398 // -- a vector of choices by priority (choiceVec)
399 // -- vectors of the choices for each instruction slot (choicesForSlot[])
400 // -- number of choices in each sched class, used to check issue conflicts
401 // between choices for a single cycle
402 //----------------------------------------------------------------------
404 inline unsigned int getNumChoices () const {
405 return choiceVec.size();
408 inline unsigned getNumChoicesInClass (const InstrSchedClass& sc) const {
409 assert(sc < numInClass.size() && "Invalid op code or sched class!");
410 return numInClass[sc];
413 inline const SchedGraphNode* getChoice(unsigned int i) const {
414 // assert(i < choiceVec.size()); don't check here.
418 inline hash_set<const SchedGraphNode*>& getChoicesForSlot(unsigned slotNum) {
419 assert(slotNum < nslots);
420 return choicesForSlot[slotNum];
423 inline void addChoice (const SchedGraphNode* node) {
424 // Append the instruction to the vector of choices for current cycle.
425 // Increment numInClass[c] for the sched class to which the instr belongs.
426 choiceVec.push_back(node);
427 const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpcode());
428 assert(sc < numInClass.size());
432 inline void addChoiceToSlot (unsigned int slotNum,
433 const SchedGraphNode* node) {
434 // Add the instruction to the choice set for the specified slot
435 assert(slotNum < nslots);
436 choicesForSlot[slotNum].insert(node);
439 inline void resetChoices () {
441 for (unsigned int s=0; s < nslots; s++)
442 choicesForSlot[s].clear();
443 for (unsigned int c=0; c < numInClass.size(); c++)
447 //----------------------------------------------------------------------
448 // Code to query and manage the partial instruction schedule so far
449 //----------------------------------------------------------------------
451 inline unsigned int getNumScheduled () const {
452 return isched.getNumInstructions();
455 inline unsigned int getNumUnscheduled() const {
456 return totalInstrCount - isched.getNumInstructions();
459 inline bool isScheduled (const SchedGraphNode* node) const {
460 return (isched.getStartTime(node->getNodeId()) >= 0);
463 inline void scheduleInstr (const SchedGraphNode* node,
464 unsigned int slotNum,
467 assert(! isScheduled(node) && "Instruction already scheduled?");
469 // add the instruction to the schedule
470 isched.scheduleInstr(node, slotNum, cycle);
472 // update the earliest start times of all nodes that conflict with `node'
473 // and the next-earliest time anything can issue if `node' causes bubbles
474 updateEarliestStartTimes(node, cycle);
476 // remove the instruction from the choice sets for all slots
477 for (unsigned s=0; s < nslots; s++)
478 choicesForSlot[s].erase(node);
480 // and decrement the instr count for the sched class to which it belongs
481 const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpcode());
482 assert(sc < numInClass.size());
486 //----------------------------------------------------------------------
487 // Create and retrieve delay slot info for delayed instructions
488 //----------------------------------------------------------------------
490 inline DelaySlotInfo* getDelaySlotInfoForInstr(const SchedGraphNode* bn,
491 bool createIfMissing=false)
493 hash_map<const SchedGraphNode*, DelaySlotInfo*>::const_iterator
494 I = delaySlotInfoForBranches.find(bn);
495 if (I != delaySlotInfoForBranches.end())
498 if (!createIfMissing) return 0;
500 DelaySlotInfo *dinfo =
501 new DelaySlotInfo(bn, getInstrInfo().getNumDelaySlots(bn->getOpcode()));
502 return delaySlotInfoForBranches[bn] = dinfo;
506 SchedulingManager(); // DISABLED: DO NOT IMPLEMENT
507 void updateEarliestStartTimes(const SchedGraphNode* node, cycles_t schedTime);
512 SchedulingManager::SchedulingManager(const TargetMachine& target,
513 const SchedGraph* graph,
514 SchedPriorities& _schedPrio)
515 : nslots(target.getSchedInfo().getMaxNumIssueTotal()),
516 schedInfo(target.getSchedInfo()),
517 schedPrio(_schedPrio),
518 isched(nslots, graph->getNumNodes()),
519 totalInstrCount(graph->getNumNodes() - 2),
520 nextEarliestIssueTime(0),
521 choicesForSlot(nslots),
522 numInClass(target.getSchedInfo().getNumSchedClasses(), 0), // set all to 0
523 nextEarliestStartTime(target.getInstrInfo().getNumOpcodes(),
524 (cycles_t) 0) // set all to 0
528 // Note that an upper bound on #choices for each slot is = nslots since
529 // we use this vector to hold a feasible set of instructions, and more
530 // would be infeasible. Reserve that much memory since it is probably small.
531 for (unsigned int i=0; i < nslots; i++)
532 choicesForSlot[i].resize(nslots);
537 SchedulingManager::updateEarliestStartTimes(const SchedGraphNode* node,
540 if (schedInfo.numBubblesAfter(node->getOpcode()) > 0)
541 { // Update next earliest time before which *nothing* can issue.
542 nextEarliestIssueTime = std::max(nextEarliestIssueTime,
543 curTime + 1 + schedInfo.numBubblesAfter(node->getOpcode()));
546 const std::vector<MachineOpCode>&
547 conflictVec = schedInfo.getConflictList(node->getOpcode());
549 for (unsigned i=0; i < conflictVec.size(); i++)
551 MachineOpCode toOp = conflictVec[i];
552 cycles_t est=schedTime + schedInfo.getMinIssueGap(node->getOpcode(),toOp);
553 assert(toOp < (int) nextEarliestStartTime.size());
554 if (nextEarliestStartTime[toOp] < est)
555 nextEarliestStartTime[toOp] = est;
559 //************************* Internal Functions *****************************/
563 AssignInstructionsToSlots(class SchedulingManager& S, unsigned maxIssue)
565 // find the slot to start from, in the current cycle
566 unsigned int startSlot = 0;
567 cycles_t curTime = S.getTime();
569 assert(maxIssue > 0 && maxIssue <= S.nslots - startSlot);
571 // If only one instruction can be issued, do so.
573 for (unsigned s=startSlot; s < S.nslots; s++)
574 if (S.getChoicesForSlot(s).size() > 0) {
575 // found the one instruction
576 S.scheduleInstr(*S.getChoicesForSlot(s).begin(), s, curTime);
580 // Otherwise, choose from the choices for each slot
582 InstrGroup* igroup = S.isched.getIGroup(S.getTime());
583 assert(igroup != NULL && "Group creation failed?");
585 // Find a slot that has only a single choice, and take it.
586 // If all slots have 0 or multiple choices, pick the first slot with
587 // choices and use its last instruction (just to avoid shifting the vector).
589 for (numIssued = 0; numIssued < maxIssue; numIssued++) {
591 for (unsigned s=startSlot; s < S.nslots; s++)
592 if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() == 1) {
593 chosenSlot = (int) s;
597 if (chosenSlot == -1)
598 for (unsigned s=startSlot; s < S.nslots; s++)
599 if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() > 0) {
600 chosenSlot = (int) s;
604 if (chosenSlot != -1) {
605 // Insert the chosen instr in the chosen slot and
606 // erase it from all slots.
607 const SchedGraphNode* node= *S.getChoicesForSlot(chosenSlot).begin();
608 S.scheduleInstr(node, chosenSlot, curTime);
612 assert(numIssued > 0 && "Should not happen when maxIssue > 0!");
617 // For now, just assume we are scheduling within a single basic block.
618 // Get the machine instruction vector for the basic block and clear it,
619 // then append instructions in scheduled order.
620 // Also, re-insert the dummy PHI instructions that were at the beginning
621 // of the basic block, since they are not part of the schedule.
624 RecordSchedule(MachineBasicBlock &MBB, const SchedulingManager& S)
626 const TargetInstrInfo& mii = S.schedInfo.getInstrInfo();
629 // Lets make sure we didn't lose any instructions, except possibly
630 // some NOPs from delay slots. Also, PHIs are not included in the schedule.
631 unsigned numInstr = 0;
632 for (MachineBasicBlock::iterator I=MBB.begin(); I != MBB.end(); ++I)
633 if (! mii.isNop(I->getOpcode()) &&
634 ! mii.isDummyPhiInstr(I->getOpcode()))
636 assert(S.isched.getNumInstructions() >= numInstr &&
637 "Lost some non-NOP instructions during scheduling!");
640 if (S.isched.getNumInstructions() == 0)
641 return; // empty basic block!
643 // First find the dummy instructions at the start of the basic block
644 MachineBasicBlock::iterator I = MBB.begin();
645 for ( ; I != MBB.end(); ++I)
646 if (! mii.isDummyPhiInstr(I->getOpcode()))
649 // Remove all except the dummy PHI instructions from MBB, and
650 // pre-allocate create space for the ones we will put back in.
651 while (I != MBB.end()) MBB.remove(I);
653 InstrSchedule::const_iterator NIend = S.isched.end();
654 for (InstrSchedule::const_iterator NI = S.isched.begin(); NI != NIend; ++NI)
655 MBB.push_back(const_cast<MachineInstr*>((*NI)->getMachineInstr()));
661 MarkSuccessorsReady(SchedulingManager& S, const SchedGraphNode* node)
663 // Check if any successors are now ready that were not already marked
664 // ready before, and that have not yet been scheduled.
666 for (sg_succ_const_iterator SI = succ_begin(node); SI !=succ_end(node); ++SI)
667 if (! (*SI)->isDummyNode()
668 && ! S.isScheduled(*SI)
669 && ! S.schedPrio.nodeIsReady(*SI))
671 // successor not scheduled and not marked ready; check *its* preds.
673 bool succIsReady = true;
674 for (sg_pred_const_iterator P=pred_begin(*SI); P != pred_end(*SI); ++P)
675 if (! (*P)->isDummyNode() && ! S.isScheduled(*P)) {
680 if (succIsReady) // add the successor to the ready list
681 S.schedPrio.insertReady(*SI);
686 // Choose up to `nslots' FEASIBLE instructions and assign each
687 // instruction to all possible slots that do not violate feasibility.
688 // FEASIBLE means it should be guaranteed that the set
689 // of chosen instructions can be issued in a single group.
692 // maxIssue : total number of feasible instructions
693 // S.choicesForSlot[i=0..nslots] : set of instructions feasible in slot i
696 FindSlotChoices(SchedulingManager& S,
697 DelaySlotInfo*& getDelaySlotInfo)
699 // initialize result vectors to empty
702 // find the slot to start from, in the current cycle
703 unsigned int startSlot = 0;
704 InstrGroup* igroup = S.isched.getIGroup(S.getTime());
705 for (int s = S.nslots - 1; s >= 0; s--)
706 if ((*igroup)[s] != NULL) {
711 // Make sure we pick at most one instruction that would break the group.
712 // Also, if we do pick one, remember which it was.
713 unsigned int indexForBreakingNode = S.nslots;
714 unsigned int indexForDelayedInstr = S.nslots;
715 DelaySlotInfo* delaySlotInfo = NULL;
717 getDelaySlotInfo = NULL;
719 // Choose instructions in order of priority.
720 // Add choices to the choice vector in the SchedulingManager class as
721 // we choose them so that subsequent choices will be correctly tested
722 // for feasibility, w.r.t. higher priority choices for the same cycle.
724 while (S.getNumChoices() < S.nslots - startSlot) {
725 const SchedGraphNode* nextNode=S.schedPrio.getNextHighest(S,S.getTime());
726 if (nextNode == NULL)
727 break; // no more instructions for this cycle
729 if (S.getInstrInfo().getNumDelaySlots(nextNode->getOpcode()) > 0) {
730 delaySlotInfo = S.getDelaySlotInfoForInstr(nextNode);
731 if (delaySlotInfo != NULL) {
732 if (indexForBreakingNode < S.nslots)
733 // cannot issue a delayed instr in the same cycle as one
734 // that breaks the issue group or as another delayed instr
737 indexForDelayedInstr = S.getNumChoices();
739 } else if (S.schedInfo.breaksIssueGroup(nextNode->getOpcode())) {
740 if (indexForBreakingNode < S.nslots)
741 // have a breaking instruction already so throw this one away
744 indexForBreakingNode = S.getNumChoices();
747 if (nextNode != NULL) {
748 S.addChoice(nextNode);
750 if (S.schedInfo.isSingleIssue(nextNode->getOpcode())) {
751 assert(S.getNumChoices() == 1 &&
752 "Prioritizer returned invalid instr for this cycle!");
757 if (indexForDelayedInstr < S.nslots)
758 break; // leave the rest for delay slots
761 assert(S.getNumChoices() <= S.nslots);
762 assert(! (indexForDelayedInstr < S.nslots &&
763 indexForBreakingNode < S.nslots) && "Cannot have both in a cycle");
765 // Assign each chosen instruction to all possible slots for that instr.
766 // But if only one instruction was chosen, put it only in the first
767 // feasible slot; no more analysis will be needed.
769 if (indexForDelayedInstr >= S.nslots &&
770 indexForBreakingNode >= S.nslots)
771 { // No instructions that break the issue group or that have delay slots.
772 // This is the common case, so handle it separately for efficiency.
774 if (S.getNumChoices() == 1) {
775 MachineOpCode opCode = S.getChoice(0)->getOpcode();
777 for (s=startSlot; s < S.nslots; s++)
778 if (S.schedInfo.instrCanUseSlot(opCode, s))
780 assert(s < S.nslots && "No feasible slot for this opCode?");
781 S.addChoiceToSlot(s, S.getChoice(0));
783 for (unsigned i=0; i < S.getNumChoices(); i++) {
784 MachineOpCode opCode = S.getChoice(i)->getOpcode();
785 for (unsigned int s=startSlot; s < S.nslots; s++)
786 if (S.schedInfo.instrCanUseSlot(opCode, s))
787 S.addChoiceToSlot(s, S.getChoice(i));
790 } else if (indexForDelayedInstr < S.nslots) {
791 // There is an instruction that needs delay slots.
792 // Try to assign that instruction to a higher slot than any other
793 // instructions in the group, so that its delay slots can go
797 assert(indexForDelayedInstr == S.getNumChoices() - 1 &&
798 "Instruction with delay slots should be last choice!");
799 assert(delaySlotInfo != NULL && "No delay slot info for instr?");
801 const SchedGraphNode* delayedNode = S.getChoice(indexForDelayedInstr);
802 MachineOpCode delayOpCode = delayedNode->getOpcode();
803 unsigned ndelays= S.getInstrInfo().getNumDelaySlots(delayOpCode);
805 unsigned delayedNodeSlot = S.nslots;
808 // Find the last possible slot for the delayed instruction that leaves
809 // at least `d' slots vacant after it (d = #delay slots)
810 for (int s = S.nslots-ndelays-1; s >= (int) startSlot; s--)
811 if (S.schedInfo.instrCanUseSlot(delayOpCode, s)) {
816 highestSlotUsed = -1;
817 for (unsigned i=0; i < S.getNumChoices() - 1; i++) {
818 // Try to assign every other instruction to a lower numbered
819 // slot than delayedNodeSlot.
820 MachineOpCode opCode =S.getChoice(i)->getOpcode();
821 bool noSlotFound = true;
823 for (s=startSlot; s < delayedNodeSlot; s++)
824 if (S.schedInfo.instrCanUseSlot(opCode, s)) {
825 S.addChoiceToSlot(s, S.getChoice(i));
829 // No slot before `delayedNodeSlot' was found for this opCode
830 // Use a later slot, and allow some delay slots to fall in
833 for ( ; s < S.nslots; s++)
834 if (S.schedInfo.instrCanUseSlot(opCode, s)) {
835 S.addChoiceToSlot(s, S.getChoice(i));
839 assert(s < S.nslots && "No feasible slot for instruction?");
841 highestSlotUsed = std::max(highestSlotUsed, (int) s);
844 assert(highestSlotUsed <= (int) S.nslots-1 && "Invalid slot used?");
846 // We will put the delayed node in the first slot after the
847 // highest slot used. But we just mark that for now, and
848 // schedule it separately because we want to schedule the delay
849 // slots for the node at the same time.
850 cycles_t dcycle = S.getTime();
851 unsigned int dslot = highestSlotUsed + 1;
852 if (dslot == S.nslots) {
856 delaySlotInfo->recordChosenSlot(dcycle, dslot);
857 getDelaySlotInfo = delaySlotInfo;
859 // There is an instruction that breaks the issue group.
860 // For such an instruction, assign to the last possible slot in
861 // the current group, and then don't assign any other instructions
863 assert(indexForBreakingNode < S.nslots);
864 const SchedGraphNode* breakingNode=S.getChoice(indexForBreakingNode);
865 unsigned breakingSlot = INT_MAX;
866 unsigned int nslotsToUse = S.nslots;
868 // Find the last possible slot for this instruction.
869 for (int s = S.nslots-1; s >= (int) startSlot; s--)
870 if (S.schedInfo.instrCanUseSlot(breakingNode->getOpcode(), s)) {
874 assert(breakingSlot < S.nslots &&
875 "No feasible slot for `breakingNode'?");
877 // Higher priority instructions than the one that breaks the group:
878 // These can be assigned to all slots, but will be assigned only
879 // to earlier slots if possible.
881 i < S.getNumChoices() && i < indexForBreakingNode; i++)
883 MachineOpCode opCode =S.getChoice(i)->getOpcode();
885 // If a higher priority instruction cannot be assigned to
886 // any earlier slots, don't schedule the breaking instruction.
888 bool foundLowerSlot = false;
889 nslotsToUse = S.nslots; // May be modified in the loop
890 for (unsigned int s=startSlot; s < nslotsToUse; s++)
891 if (S.schedInfo.instrCanUseSlot(opCode, s)) {
892 if (breakingSlot < S.nslots && s < breakingSlot) {
893 foundLowerSlot = true;
894 nslotsToUse = breakingSlot; // RESETS LOOP UPPER BOUND!
897 S.addChoiceToSlot(s, S.getChoice(i));
901 breakingSlot = INT_MAX; // disable breaking instr
904 // Assign the breaking instruction (if any) to a single slot
905 // Otherwise, just ignore the instruction. It will simply be
906 // scheduled in a later cycle.
907 if (breakingSlot < S.nslots) {
908 S.addChoiceToSlot(breakingSlot, breakingNode);
909 nslotsToUse = breakingSlot;
911 nslotsToUse = S.nslots;
913 // For lower priority instructions than the one that breaks the
914 // group, only assign them to slots lower than the breaking slot.
915 // Otherwise, just ignore the instruction.
916 for (unsigned i=indexForBreakingNode+1; i < S.getNumChoices(); i++) {
917 MachineOpCode opCode = S.getChoice(i)->getOpcode();
918 for (unsigned int s=startSlot; s < nslotsToUse; s++)
919 if (S.schedInfo.instrCanUseSlot(opCode, s))
920 S.addChoiceToSlot(s, S.getChoice(i));
922 } // endif (no delay slots and no breaking slots)
924 return S.getNumChoices();
929 ChooseOneGroup(SchedulingManager& S)
931 assert(S.schedPrio.getNumReady() > 0
932 && "Don't get here without ready instructions.");
934 cycles_t firstCycle = S.getTime();
935 DelaySlotInfo* getDelaySlotInfo = NULL;
937 // Choose up to `nslots' feasible instructions and their possible slots.
938 unsigned numIssued = FindSlotChoices(S, getDelaySlotInfo);
940 while (numIssued == 0) {
941 S.updateTime(S.getTime()+1);
942 numIssued = FindSlotChoices(S, getDelaySlotInfo);
945 AssignInstructionsToSlots(S, numIssued);
947 if (getDelaySlotInfo != NULL)
948 numIssued += getDelaySlotInfo->scheduleDelayedNode(S);
950 // Print trace of scheduled instructions before newly ready ones
951 if (SchedDebugLevel >= Sched_PrintSchedTrace) {
952 for (cycles_t c = firstCycle; c <= S.getTime(); c++) {
953 std::cerr << " Cycle " << (long)c <<" : Scheduled instructions:\n";
954 const InstrGroup* igroup = S.isched.getIGroup(c);
955 for (unsigned int s=0; s < S.nslots; s++) {
957 if ((*igroup)[s] != NULL)
958 std::cerr << * ((*igroup)[s])->getMachineInstr() << "\n";
960 std::cerr << "<none>\n";
970 ForwardListSchedule(SchedulingManager& S)
973 const SchedGraphNode* node;
975 S.schedPrio.initialize();
977 while ((N = S.schedPrio.getNumReady()) > 0) {
978 cycles_t nextCycle = S.getTime();
980 // Choose one group of instructions for a cycle, plus any delay slot
981 // instructions (which may overflow into successive cycles).
982 // This will advance S.getTime() to the last cycle in which
983 // instructions are actually issued.
985 unsigned numIssued = ChooseOneGroup(S);
986 assert(numIssued > 0 && "Deadlock in list scheduling algorithm?");
988 // Notify the priority manager of scheduled instructions and mark
989 // any successors that may now be ready
991 for (cycles_t c = nextCycle; c <= S.getTime(); c++) {
992 const InstrGroup* igroup = S.isched.getIGroup(c);
993 for (unsigned int s=0; s < S.nslots; s++)
994 if ((node = (*igroup)[s]) != NULL) {
995 S.schedPrio.issuedReadyNodeAt(S.getTime(), node);
996 MarkSuccessorsReady(S, node);
1000 // Move to the next the next earliest cycle for which
1001 // an instruction can be issued, or the next earliest in which
1002 // one will be ready, or to the next cycle, whichever is latest.
1004 S.updateTime(std::max(S.getTime() + 1,
1005 std::max(S.getEarliestIssueTime(),
1006 S.schedPrio.getEarliestReadyTime())));
1011 //---------------------------------------------------------------------
1012 // Code for filling delay slots for delayed terminator instructions
1013 // (e.g., BRANCH and RETURN). Delay slots for non-terminator
1014 // instructions (e.g., CALL) are not handled here because they almost
1015 // always can be filled with instructions from the call sequence code
1016 // before a call. That's preferable because we incur many tradeoffs here
1017 // when we cannot find single-cycle instructions that can be reordered.
1018 //----------------------------------------------------------------------
1021 NodeCanFillDelaySlot(const SchedulingManager& S,
1022 const SchedGraphNode* node,
1023 const SchedGraphNode* brNode,
1024 bool nodeIsPredecessor)
1026 assert(! node->isDummyNode());
1028 // don't put a branch in the delay slot of another branch
1029 if (S.getInstrInfo().isBranch(node->getOpcode()))
1032 // don't put a single-issue instruction in the delay slot of a branch
1033 if (S.schedInfo.isSingleIssue(node->getOpcode()))
1036 // don't put a load-use dependence in the delay slot of a branch
1037 const TargetInstrInfo& mii = S.getInstrInfo();
1039 for (SchedGraphNode::const_iterator EI = node->beginInEdges();
1040 EI != node->endInEdges(); ++EI)
1041 if (! ((SchedGraphNode*)(*EI)->getSrc())->isDummyNode()
1042 && mii.isLoad(((SchedGraphNode*)(*EI)->getSrc())->getOpcode())
1043 && (*EI)->getDepType() == SchedGraphEdge::CtrlDep)
1046 // for now, don't put an instruction that does not have operand
1047 // interlocks in the delay slot of a branch
1048 if (! S.getInstrInfo().hasOperandInterlock(node->getOpcode()))
1051 // Finally, if the instruction precedes the branch, we make sure the
1052 // instruction can be reordered relative to the branch. We simply check
1053 // if the instr. has only 1 outgoing edge, viz., a CD edge to the branch.
1055 if (nodeIsPredecessor) {
1056 bool onlyCDEdgeToBranch = true;
1057 for (SchedGraphNode::const_iterator OEI = node->beginOutEdges();
1058 OEI != node->endOutEdges(); ++OEI)
1059 if (! ((SchedGraphNode*)(*OEI)->getSink())->isDummyNode()
1060 && ((*OEI)->getSink() != brNode
1061 || (*OEI)->getDepType() != SchedGraphEdge::CtrlDep))
1063 onlyCDEdgeToBranch = false;
1067 if (!onlyCDEdgeToBranch)
1076 MarkNodeForDelaySlot(SchedulingManager& S,
1078 SchedGraphNode* node,
1079 const SchedGraphNode* brNode,
1080 bool nodeIsPredecessor)
1082 if (nodeIsPredecessor) {
1083 // If node is in the same basic block (i.e., precedes brNode),
1084 // remove it and all its incident edges from the graph. Make sure we
1085 // add dummy edges for pred/succ nodes that become entry/exit nodes.
1086 graph->eraseIncidentEdges(node, /*addDummyEdges*/ true);
1088 // If the node was from a target block, add the node to the graph
1089 // and add a CD edge from brNode to node.
1090 assert(0 && "NOT IMPLEMENTED YET");
1093 DelaySlotInfo* dinfo = S.getDelaySlotInfoForInstr(brNode, /*create*/ true);
1094 dinfo->addDelayNode(node);
1099 FindUsefulInstructionsForDelaySlots(SchedulingManager& S,
1100 SchedGraphNode* brNode,
1101 std::vector<SchedGraphNode*>& sdelayNodeVec)
1103 const TargetInstrInfo& mii = S.getInstrInfo();
1105 mii.getNumDelaySlots(brNode->getOpcode());
1110 sdelayNodeVec.reserve(ndelays);
1112 // Use a separate vector to hold the feasible multi-cycle nodes.
1113 // These will be used if not enough single-cycle nodes are found.
1115 std::vector<SchedGraphNode*> mdelayNodeVec;
1117 for (sg_pred_iterator P = pred_begin(brNode);
1118 P != pred_end(brNode) && sdelayNodeVec.size() < ndelays; ++P)
1119 if (! (*P)->isDummyNode() &&
1120 ! mii.isNop((*P)->getOpcode()) &&
1121 NodeCanFillDelaySlot(S, *P, brNode, /*pred*/ true))
1123 if (mii.maxLatency((*P)->getOpcode()) > 1)
1124 mdelayNodeVec.push_back(*P);
1126 sdelayNodeVec.push_back(*P);
1129 // If not enough single-cycle instructions were found, select the
1130 // lowest-latency multi-cycle instructions and use them.
1131 // Note that this is the most efficient code when only 1 (or even 2)
1132 // values need to be selected.
1134 while (sdelayNodeVec.size() < ndelays && mdelayNodeVec.size() > 0) {
1136 mii.maxLatency(mdelayNodeVec[0]->getOpcode());
1137 unsigned minIndex = 0;
1138 for (unsigned i=1; i < mdelayNodeVec.size(); i++)
1141 mii.maxLatency(mdelayNodeVec[i]->getOpcode());
1148 sdelayNodeVec.push_back(mdelayNodeVec[minIndex]);
1149 if (sdelayNodeVec.size() < ndelays) // avoid the last erase!
1150 mdelayNodeVec.erase(mdelayNodeVec.begin() + minIndex);
1155 // Remove the NOPs currently in delay slots from the graph.
1156 // Mark instructions specified in sdelayNodeVec to replace them.
1157 // If not enough useful instructions were found, mark the NOPs to be used
1158 // for filling delay slots, otherwise, otherwise just discard them.
1160 static void ReplaceNopsWithUsefulInstr(SchedulingManager& S,
1161 SchedGraphNode* node,
1162 // FIXME: passing vector BY VALUE!!!
1163 std::vector<SchedGraphNode*> sdelayNodeVec,
1166 std::vector<SchedGraphNode*> nopNodeVec; // this will hold unused NOPs
1167 const TargetInstrInfo& mii = S.getInstrInfo();
1168 const MachineInstr* brInstr = node->getMachineInstr();
1169 unsigned ndelays= mii.getNumDelaySlots(brInstr->getOpcode());
1170 assert(ndelays > 0 && "Unnecessary call to replace NOPs");
1172 // Remove the NOPs currently in delay slots from the graph.
1173 // If not enough useful instructions were found, use the NOPs to
1174 // fill delay slots, otherwise, just discard them.
1176 unsigned int firstDelaySlotIdx = node->getOrigIndexInBB() + 1;
1177 MachineBasicBlock& MBB = node->getMachineBasicBlock();
1178 MachineBasicBlock::iterator MBBI = MBB.begin();
1179 std::advance(MBBI, firstDelaySlotIdx - 1);
1180 assert(&*MBBI++ == brInstr &&
1181 "Incorrect instr. index in basic block for brInstr");
1183 // First find all useful instructions already in the delay slots
1184 // and USE THEM. We'll throw away the unused alternatives below
1186 MachineBasicBlock::iterator Tmp = MBBI;
1187 for (unsigned i = 0; i != ndelays; ++i, ++MBBI)
1188 if (!mii.isNop(MBBI->getOpcode()))
1189 sdelayNodeVec.insert(sdelayNodeVec.begin(),
1190 graph->getGraphNodeForInstr(MBBI));
1193 // Then find the NOPs and keep only as many as are needed.
1194 // Put the rest in nopNodeVec to be deleted.
1195 for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx+ndelays; ++i, ++MBBI)
1196 if (mii.isNop(MBBI->getOpcode()))
1197 if (sdelayNodeVec.size() < ndelays)
1198 sdelayNodeVec.push_back(graph->getGraphNodeForInstr(MBBI));
1200 nopNodeVec.push_back(graph->getGraphNodeForInstr(MBBI));
1202 //remove the MI from the Machine Code For Instruction
1203 const TerminatorInst *TI = MBB.getBasicBlock()->getTerminator();
1204 MachineCodeForInstruction& llvmMvec =
1205 MachineCodeForInstruction::get((const Instruction *)TI);
1207 for(MachineCodeForInstruction::iterator mciI=llvmMvec.begin(),
1208 mciE=llvmMvec.end(); mciI!=mciE; ++mciI){
1210 llvmMvec.erase(mciI);
1214 assert(sdelayNodeVec.size() >= ndelays);
1216 // If some delay slots were already filled, throw away that many new choices
1217 if (sdelayNodeVec.size() > ndelays)
1218 sdelayNodeVec.resize(ndelays);
1220 // Mark the nodes chosen for delay slots. This removes them from the graph.
1221 for (unsigned i=0; i < sdelayNodeVec.size(); i++)
1222 MarkNodeForDelaySlot(S, graph, sdelayNodeVec[i], node, true);
1224 // And remove the unused NOPs from the graph.
1225 for (unsigned i=0; i < nopNodeVec.size(); i++)
1226 graph->eraseIncidentEdges(nopNodeVec[i], /*addDummyEdges*/ true);
1230 // For all delayed instructions, choose instructions to put in the delay
1231 // slots and pull those out of the graph. Mark them for the delay slots
1232 // in the DelaySlotInfo object for that graph node. If no useful work
1233 // is found for a delay slot, use the NOP that is currently in that slot.
1235 // We try to fill the delay slots with useful work for all instructions
1236 // EXCEPT CALLS AND RETURNS.
1237 // For CALLs and RETURNs, it is nearly always possible to use one of the
1238 // call sequence instrs and putting anything else in the delay slot could be
1239 // suboptimal. Also, it complicates generating the calling sequence code in
1243 ChooseInstructionsForDelaySlots(SchedulingManager& S, MachineBasicBlock &MBB,
1246 const TargetInstrInfo& mii = S.getInstrInfo();
1248 Instruction *termInstr = (Instruction*)MBB.getBasicBlock()->getTerminator();
1249 MachineCodeForInstruction &termMvec=MachineCodeForInstruction::get(termInstr);
1250 std::vector<SchedGraphNode*> delayNodeVec;
1251 const MachineInstr* brInstr = NULL;
1253 if (EnableFillingDelaySlots &&
1254 termInstr->getOpcode() != Instruction::Ret)
1256 // To find instructions that need delay slots without searching the full
1257 // machine code, we assume that the only delayed instructions are CALLs
1258 // or instructions generated for the terminator inst.
1259 // Find the first branch instr in the sequence of machine instrs for term
1262 while (first < termMvec.size() &&
1263 ! mii.isBranch(termMvec[first]->getOpcode()))
1267 assert(first < termMvec.size() &&
1268 "No branch instructions for BR? Ok, but weird! Delete assertion.");
1270 brInstr = (first < termMvec.size())? termMvec[first] : NULL;
1272 // Compute a vector of the nodes chosen for delay slots and then
1273 // mark delay slots to replace NOPs with these useful instructions.
1275 if (brInstr != NULL) {
1276 SchedGraphNode* brNode = graph->getGraphNodeForInstr(brInstr);
1277 FindUsefulInstructionsForDelaySlots(S, brNode, delayNodeVec);
1278 ReplaceNopsWithUsefulInstr(S, brNode, delayNodeVec, graph);
1282 // Also mark delay slots for other delayed instructions to hold NOPs.
1283 // Simply passing in an empty delayNodeVec will have this effect.
1284 // If brInstr is not handled above (EnableFillingDelaySlots == false),
1285 // brInstr will be NULL so this will handle the branch instrs. as well.
1287 delayNodeVec.clear();
1288 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ++I)
1289 if (I != brInstr && mii.getNumDelaySlots(I->getOpcode()) > 0) {
1290 SchedGraphNode* node = graph->getGraphNodeForInstr(I);
1291 ReplaceNopsWithUsefulInstr(S, node, delayNodeVec, graph);
1297 // Schedule the delayed branch and its delay slots
1300 DelaySlotInfo::scheduleDelayedNode(SchedulingManager& S)
1302 assert(delayedNodeSlotNum < S.nslots && "Illegal slot for branch");
1303 assert(S.isched.getInstr(delayedNodeSlotNum, delayedNodeCycle) == NULL
1304 && "Slot for branch should be empty");
1306 unsigned int nextSlot = delayedNodeSlotNum;
1307 cycles_t nextTime = delayedNodeCycle;
1309 S.scheduleInstr(brNode, nextSlot, nextTime);
1311 for (unsigned d=0; d < ndelays; d++) {
1313 if (nextSlot == S.nslots) {
1318 // Find the first feasible instruction for this delay slot
1319 // Note that we only check for issue restrictions here.
1320 // We do *not* check for flow dependences but rely on pipeline
1321 // interlocks to resolve them. Machines without interlocks
1322 // will require this code to be modified.
1323 for (unsigned i=0; i < delayNodeVec.size(); i++) {
1324 const SchedGraphNode* dnode = delayNodeVec[i];
1325 if ( ! S.isScheduled(dnode)
1326 && S.schedInfo.instrCanUseSlot(dnode->getOpcode(), nextSlot)
1327 && instrIsFeasible(S, dnode->getOpcode()))
1329 assert(S.getInstrInfo().hasOperandInterlock(dnode->getOpcode())
1330 && "Instructions without interlocks not yet supported "
1331 "when filling branch delay slots");
1332 S.scheduleInstr(dnode, nextSlot, nextTime);
1338 // Update current time if delay slots overflowed into later cycles.
1339 // Do this here because we know exactly which cycle is the last cycle
1340 // that contains delay slots. The next loop doesn't compute that.
1341 if (nextTime > S.getTime())
1342 S.updateTime(nextTime);
1344 // Now put any remaining instructions in the unfilled delay slots.
1345 // This could lead to suboptimal performance but needed for correctness.
1346 nextSlot = delayedNodeSlotNum;
1347 nextTime = delayedNodeCycle;
1348 for (unsigned i=0; i < delayNodeVec.size(); i++)
1349 if (! S.isScheduled(delayNodeVec[i])) {
1350 do { // find the next empty slot
1352 if (nextSlot == S.nslots) {
1356 } while (S.isched.getInstr(nextSlot, nextTime) != NULL);
1358 S.scheduleInstr(delayNodeVec[i], nextSlot, nextTime);
1366 // Check if the instruction would conflict with instructions already
1367 // chosen for the current cycle
1370 ConflictsWithChoices(const SchedulingManager& S,
1371 MachineOpCode opCode)
1373 // Check if the instruction must issue by itself, and some feasible
1374 // choices have already been made for this cycle
1375 if (S.getNumChoices() > 0 && S.schedInfo.isSingleIssue(opCode))
1378 // For each class that opCode belongs to, check if there are too many
1379 // instructions of that class.
1381 const InstrSchedClass sc = S.schedInfo.getSchedClass(opCode);
1382 return (S.getNumChoicesInClass(sc) == S.schedInfo.getMaxIssueForClass(sc));
1386 //************************* External Functions *****************************/
1389 //---------------------------------------------------------------------------
1390 // Function: ViolatesMinimumGap
1393 // Check minimum gap requirements relative to instructions scheduled in
1395 // Note that we do not need to consider `nextEarliestIssueTime' here because
1396 // that is also captured in the earliest start times for each opcode.
1397 //---------------------------------------------------------------------------
1400 ViolatesMinimumGap(const SchedulingManager& S,
1401 MachineOpCode opCode,
1402 const cycles_t inCycle)
1404 return (inCycle < S.getEarliestStartTimeForOp(opCode));
1408 //---------------------------------------------------------------------------
1409 // Function: instrIsFeasible
1412 // Check if any issue restrictions would prevent the instruction from
1413 // being issued in the current cycle
1414 //---------------------------------------------------------------------------
1417 instrIsFeasible(const SchedulingManager& S,
1418 MachineOpCode opCode)
1420 // skip the instruction if it cannot be issued due to issue restrictions
1421 // caused by previously issued instructions
1422 if (ViolatesMinimumGap(S, opCode, S.getTime()))
1425 // skip the instruction if it cannot be issued due to issue restrictions
1426 // caused by previously chosen instructions for the current cycle
1427 if (ConflictsWithChoices(S, opCode))
1433 //---------------------------------------------------------------------------
1434 // Function: ScheduleInstructionsWithSSA
1437 // Entry point for instruction scheduling on SSA form.
1438 // Schedules the machine instructions generated by instruction selection.
1439 // Assumes that register allocation has not been done, i.e., operands
1440 // are still in SSA form.
1441 //---------------------------------------------------------------------------
1444 class InstructionSchedulingWithSSA : public FunctionPass {
1445 const TargetMachine ⌖
1447 inline InstructionSchedulingWithSSA(const TargetMachine &T) : target(T) {}
1449 const char *getPassName() const { return "Instruction Scheduling"; }
1451 // getAnalysisUsage - We use LiveVarInfo...
1452 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1453 AU.addRequired<FunctionLiveVarInfo>();
1454 AU.setPreservesCFG();
1457 bool runOnFunction(Function &F);
1459 } // end anonymous namespace
1462 bool InstructionSchedulingWithSSA::runOnFunction(Function &F)
1464 SchedGraphSet graphSet(&F, target);
1466 if (SchedDebugLevel >= Sched_PrintSchedGraphs) {
1467 std::cerr << "\n*** SCHEDULING GRAPHS FOR INSTRUCTION SCHEDULING\n";
1471 for (SchedGraphSet::const_iterator GI=graphSet.begin(), GE=graphSet.end();
1474 SchedGraph* graph = (*GI);
1475 MachineBasicBlock &MBB = graph->getBasicBlock();
1477 if (SchedDebugLevel >= Sched_PrintSchedTrace)
1478 std::cerr << "\n*** TRACE OF INSTRUCTION SCHEDULING OPERATIONS\n\n";
1481 SchedPriorities schedPrio(&F, graph, getAnalysis<FunctionLiveVarInfo>());
1482 SchedulingManager S(target, graph, schedPrio);
1484 ChooseInstructionsForDelaySlots(S, MBB, graph); // modifies graph
1485 ForwardListSchedule(S); // computes schedule in S
1486 RecordSchedule(MBB, S); // records schedule in BB
1489 if (SchedDebugLevel >= Sched_PrintMachineCode) {
1490 std::cerr << "\n*** Machine instructions after INSTRUCTION SCHEDULING\n";
1491 MachineFunction::get(&F).dump();
1498 FunctionPass *createInstructionSchedulingWithSSAPass(const TargetMachine &tgt) {
1499 return new InstructionSchedulingWithSSA(tgt);
1502 } // End llvm namespace