- Cleaned up the interface to AnalysisUsage to take analysis class names
[oota-llvm.git] / lib / Target / SparcV9 / InstrSched / InstrScheduling.cpp
1 //===- InstrScheduling.cpp - Generic Instruction Scheduling support -------===//
2 //
3 // This file implements the llvm/CodeGen/InstrScheduling.h interface, along with
4 // generic support routines for instruction scheduling.
5 //
6 //===----------------------------------------------------------------------===//
7
8 #include "SchedPriorities.h"
9 #include "llvm/CodeGen/MachineInstr.h"
10 #include "llvm/CodeGen/MachineCodeForInstruction.h"
11 #include "llvm/CodeGen/MachineCodeForBasicBlock.h"
12 #include "llvm/CodeGen/MachineCodeForMethod.h"
13 #include "llvm/Analysis/LiveVar/FunctionLiveVarInfo.h" // FIXME: Remove when modularized better
14 #include "llvm/Target/TargetMachine.h"
15 #include "llvm/BasicBlock.h"
16 #include "llvm/Instruction.h"
17 #include "Support/CommandLine.h"
18 #include <algorithm>
19 using std::cerr;
20 using std::vector;
21
22 SchedDebugLevel_t SchedDebugLevel;
23
24 static cl::opt<SchedDebugLevel_t, true>
25 SDL_opt("dsched", cl::Hidden, cl::location(SchedDebugLevel),
26         cl::desc("enable instruction scheduling debugging information"),
27         cl::values(
28  clEnumValN(Sched_NoDebugInfo,      "n", "disable debug output"),
29  clEnumValN(Sched_Disable,        "off", "disable instruction scheduling"),
30  clEnumValN(Sched_PrintMachineCode, "y", "print machine code after scheduling"),
31  clEnumValN(Sched_PrintSchedTrace,  "t", "print trace of scheduling actions"),
32  clEnumValN(Sched_PrintSchedGraphs, "g", "print scheduling graphs"),
33                    0));
34
35
36 //************************* Internal Data Types *****************************/
37
38 class InstrSchedule;
39 class SchedulingManager;
40
41
42 //----------------------------------------------------------------------
43 // class InstrGroup:
44 // 
45 // Represents a group of instructions scheduled to be issued
46 // in a single cycle.
47 //----------------------------------------------------------------------
48
49 class InstrGroup: public NonCopyable {
50 public:
51   inline const SchedGraphNode* operator[](unsigned int slotNum) const {
52     assert(slotNum  < group.size());
53     return group[slotNum];
54   }
55   
56 private:
57   friend class InstrSchedule;
58   
59   inline void   addInstr(const SchedGraphNode* node, unsigned int slotNum) {
60     assert(slotNum < group.size());
61     group[slotNum] = node;
62   }
63   
64   /*ctor*/      InstrGroup(unsigned int nslots)
65     : group(nslots, NULL) {}
66   
67   /*ctor*/      InstrGroup();           // disable: DO NOT IMPLEMENT
68   
69 private:
70   vector<const SchedGraphNode*> group;
71 };
72
73
74 //----------------------------------------------------------------------
75 // class ScheduleIterator:
76 // 
77 // Iterates over the machine instructions in the for a single basic block.
78 // The schedule is represented by an InstrSchedule object.
79 //----------------------------------------------------------------------
80
81 template<class _NodeType>
82 class ScheduleIterator : public forward_iterator<_NodeType, ptrdiff_t> {
83 private:
84   unsigned cycleNum;
85   unsigned slotNum;
86   const InstrSchedule& S;
87 public:
88   typedef ScheduleIterator<_NodeType> _Self;
89   
90   /*ctor*/ inline ScheduleIterator(const InstrSchedule& _schedule,
91                                    unsigned _cycleNum,
92                                    unsigned _slotNum)
93     : cycleNum(_cycleNum), slotNum(_slotNum), S(_schedule) {
94     skipToNextInstr(); 
95   }
96   
97   /*ctor*/ inline ScheduleIterator(const _Self& x)
98     : cycleNum(x.cycleNum), slotNum(x.slotNum), S(x.S) {}
99   
100   inline bool operator==(const _Self& x) const {
101     return (slotNum == x.slotNum && cycleNum== x.cycleNum && &S==&x.S);
102   }
103   
104   inline bool operator!=(const _Self& x) const { return !operator==(x); }
105   
106   inline _NodeType* operator*() const {
107     assert(cycleNum < S.groups.size());
108     return (*S.groups[cycleNum])[slotNum];
109   }
110   inline _NodeType* operator->() const { return operator*(); }
111   
112          _Self& operator++();                           // Preincrement
113   inline _Self operator++(int) {                        // Postincrement
114     _Self tmp(*this); ++*this; return tmp; 
115   }
116   
117   static _Self begin(const InstrSchedule& _schedule);
118   static _Self end(  const InstrSchedule& _schedule);
119   
120 private:
121   inline _Self& operator=(const _Self& x); // DISABLE -- DO NOT IMPLEMENT
122   void  skipToNextInstr();
123 };
124
125
126 //----------------------------------------------------------------------
127 // class InstrSchedule:
128 // 
129 // Represents the schedule of machine instructions for a single basic block.
130 //----------------------------------------------------------------------
131
132 class InstrSchedule: public NonCopyable {
133 private:
134   const unsigned int nslots;
135   unsigned int numInstr;
136   vector<InstrGroup*> groups;           // indexed by cycle number
137   vector<cycles_t> startTime;           // indexed by node id
138   
139 public: // iterators
140   typedef ScheduleIterator<SchedGraphNode> iterator;
141   typedef ScheduleIterator<const SchedGraphNode> const_iterator;
142   
143         iterator begin();
144   const_iterator begin() const;
145         iterator end();
146   const_iterator end()   const;
147   
148 public: // constructors and destructor
149   /*ctor*/              InstrSchedule   (unsigned int _nslots,
150                                          unsigned int _numNodes);
151   /*dtor*/              ~InstrSchedule  ();
152   
153 public: // accessor functions to query chosen schedule
154   const SchedGraphNode* getInstr        (unsigned int slotNum,
155                                          cycles_t c) const {
156     const InstrGroup* igroup = this->getIGroup(c);
157     return (igroup == NULL)? NULL : (*igroup)[slotNum];
158   }
159   
160   inline InstrGroup*    getIGroup       (cycles_t c) {
161     if ((unsigned)c >= groups.size())
162       groups.resize(c+1);
163     if (groups[c] == NULL)
164       groups[c] = new InstrGroup(nslots);
165     return groups[c];
166   }
167   
168   inline const InstrGroup* getIGroup    (cycles_t c) const {
169     assert((unsigned)c < groups.size());
170     return groups[c];
171   }
172   
173   inline cycles_t       getStartTime    (unsigned int nodeId) const {
174     assert(nodeId < startTime.size());
175     return startTime[nodeId];
176   }
177   
178   unsigned int          getNumInstructions() const {
179     return numInstr;
180   }
181   
182   inline void           scheduleInstr   (const SchedGraphNode* node,
183                                          unsigned int slotNum,
184                                          cycles_t cycle) {
185     InstrGroup* igroup = this->getIGroup(cycle);
186     assert((*igroup)[slotNum] == NULL &&  "Slot already filled?");
187     igroup->addInstr(node, slotNum);
188     assert(node->getNodeId() < startTime.size());
189     startTime[node->getNodeId()] = cycle;
190     ++numInstr;
191   }
192   
193 private:
194   friend class iterator;
195   friend class const_iterator;
196   /*ctor*/      InstrSchedule   ();     // Disable: DO NOT IMPLEMENT.
197 };
198
199
200 /*ctor*/
201 InstrSchedule::InstrSchedule(unsigned int _nslots, unsigned int _numNodes)
202   : nslots(_nslots),
203     numInstr(0),
204     groups(2 * _numNodes / _nslots),            // 2 x lower-bound for #cycles
205     startTime(_numNodes, (cycles_t) -1)         // set all to -1
206 {
207 }
208
209
210 /*dtor*/
211 InstrSchedule::~InstrSchedule()
212 {
213   for (unsigned c=0, NC=groups.size(); c < NC; c++)
214     if (groups[c] != NULL)
215       delete groups[c];                 // delete InstrGroup objects
216 }
217
218
219 template<class _NodeType>
220 inline 
221 void
222 ScheduleIterator<_NodeType>::skipToNextInstr()
223 {
224   while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
225     ++cycleNum;                 // skip cycles with no instructions
226   
227   while (cycleNum < S.groups.size() &&
228          (*S.groups[cycleNum])[slotNum] == NULL)
229     {
230       ++slotNum;
231       if (slotNum == S.nslots)
232         {
233           ++cycleNum;
234           slotNum = 0;
235           while(cycleNum < S.groups.size() && S.groups[cycleNum] == NULL)
236             ++cycleNum;                 // skip cycles with no instructions
237         }
238     }
239 }
240
241 template<class _NodeType>
242 inline 
243 ScheduleIterator<_NodeType>&
244 ScheduleIterator<_NodeType>::operator++()       // Preincrement
245 {
246   ++slotNum;
247   if (slotNum == S.nslots)
248     {
249       ++cycleNum;
250       slotNum = 0;
251     }
252   skipToNextInstr(); 
253   return *this;
254 }
255
256 template<class _NodeType>
257 ScheduleIterator<_NodeType>
258 ScheduleIterator<_NodeType>::begin(const InstrSchedule& _schedule)
259 {
260   return _Self(_schedule, 0, 0);
261 }
262
263 template<class _NodeType>
264 ScheduleIterator<_NodeType>
265 ScheduleIterator<_NodeType>::end(const InstrSchedule& _schedule)
266 {
267   return _Self(_schedule, _schedule.groups.size(), 0);
268 }
269
270 InstrSchedule::iterator
271 InstrSchedule::begin()
272 {
273   return iterator::begin(*this);
274 }
275
276 InstrSchedule::const_iterator
277 InstrSchedule::begin() const
278 {
279   return const_iterator::begin(*this);
280 }
281
282 InstrSchedule::iterator
283 InstrSchedule::end()
284 {
285   return iterator::end(*this);
286 }
287
288 InstrSchedule::const_iterator
289 InstrSchedule::end() const
290 {
291   return const_iterator::end(  *this);
292 }
293
294
295 //----------------------------------------------------------------------
296 // class DelaySlotInfo:
297 // 
298 // Record information about delay slots for a single branch instruction.
299 // Delay slots are simply indexed by slot number 1 ... numDelaySlots
300 //----------------------------------------------------------------------
301
302 class DelaySlotInfo: public NonCopyable {
303 private:
304   const SchedGraphNode* brNode;
305   unsigned int ndelays;
306   vector<const SchedGraphNode*> delayNodeVec;
307   cycles_t delayedNodeCycle;
308   unsigned int delayedNodeSlotNum;
309   
310 public:
311   /*ctor*/      DelaySlotInfo           (const SchedGraphNode* _brNode,
312                                          unsigned _ndelays)
313     : brNode(_brNode), ndelays(_ndelays),
314       delayedNodeCycle(0), delayedNodeSlotNum(0) {}
315   
316   inline unsigned getNumDelays  () {
317     return ndelays;
318   }
319   
320   inline const vector<const SchedGraphNode*>& getDelayNodeVec() {
321     return delayNodeVec;
322   }
323   
324   inline void   addDelayNode            (const SchedGraphNode* node) {
325     delayNodeVec.push_back(node);
326     assert(delayNodeVec.size() <= ndelays && "Too many delay slot instrs!");
327   }
328   
329   inline void   recordChosenSlot        (cycles_t cycle, unsigned slotNum) {
330     delayedNodeCycle = cycle;
331     delayedNodeSlotNum = slotNum;
332   }
333   
334   unsigned      scheduleDelayedNode     (SchedulingManager& S);
335 };
336
337
338 //----------------------------------------------------------------------
339 // class SchedulingManager:
340 // 
341 // Represents the schedule of machine instructions for a single basic block.
342 //----------------------------------------------------------------------
343
344 class SchedulingManager: public NonCopyable {
345 public: // publicly accessible data members
346   const unsigned int nslots;
347   const MachineSchedInfo& schedInfo;
348   SchedPriorities& schedPrio;
349   InstrSchedule isched;
350   
351 private:
352   unsigned int totalInstrCount;
353   cycles_t curTime;
354   cycles_t nextEarliestIssueTime;               // next cycle we can issue
355   vector<hash_set<const SchedGraphNode*> > choicesForSlot; // indexed by slot#
356   vector<const SchedGraphNode*> choiceVec;      // indexed by node ptr
357   vector<int> numInClass;                       // indexed by sched class
358   vector<cycles_t> nextEarliestStartTime;       // indexed by opCode
359   hash_map<const SchedGraphNode*, DelaySlotInfo*> delaySlotInfoForBranches;
360                                                 // indexed by branch node ptr 
361   
362 public:
363   SchedulingManager(const TargetMachine& _target, const SchedGraph* graph,
364                     SchedPriorities& schedPrio);
365   ~SchedulingManager() {
366     for (hash_map<const SchedGraphNode*,
367            DelaySlotInfo*>::iterator I = delaySlotInfoForBranches.begin(),
368            E = delaySlotInfoForBranches.end(); I != E; ++I)
369       delete I->second;
370   }
371   
372   //----------------------------------------------------------------------
373   // Simplify access to the machine instruction info
374   //----------------------------------------------------------------------
375   
376   inline const MachineInstrInfo& getInstrInfo   () const {
377     return schedInfo.getInstrInfo();
378   }
379   
380   //----------------------------------------------------------------------
381   // Interface for checking and updating the current time
382   //----------------------------------------------------------------------
383   
384   inline cycles_t       getTime                 () const {
385     return curTime;
386   }
387   
388   inline cycles_t       getEarliestIssueTime() const {
389     return nextEarliestIssueTime;
390   }
391   
392   inline cycles_t       getEarliestStartTimeForOp(MachineOpCode opCode) const {
393     assert(opCode < (int) nextEarliestStartTime.size());
394     return nextEarliestStartTime[opCode];
395   }
396   
397   // Update current time to specified cycle
398   inline void   updateTime              (cycles_t c) {
399     curTime = c;
400     schedPrio.updateTime(c);
401   }
402   
403   //----------------------------------------------------------------------
404   // Functions to manage the choices for the current cycle including:
405   // -- a vector of choices by priority (choiceVec)
406   // -- vectors of the choices for each instruction slot (choicesForSlot[])
407   // -- number of choices in each sched class, used to check issue conflicts
408   //    between choices for a single cycle
409   //----------------------------------------------------------------------
410   
411   inline unsigned int getNumChoices     () const {
412     return choiceVec.size();
413   }
414   
415   inline unsigned getNumChoicesInClass  (const InstrSchedClass& sc) const {
416     assert(sc < (int) numInClass.size() && "Invalid op code or sched class!");
417     return numInClass[sc];
418   }
419   
420   inline const SchedGraphNode* getChoice(unsigned int i) const {
421     // assert(i < choiceVec.size());    don't check here.
422     return choiceVec[i];
423   }
424   
425   inline hash_set<const SchedGraphNode*>& getChoicesForSlot(unsigned slotNum) {
426     assert(slotNum < nslots);
427     return choicesForSlot[slotNum];
428   }
429   
430   inline void   addChoice               (const SchedGraphNode* node) {
431     // Append the instruction to the vector of choices for current cycle.
432     // Increment numInClass[c] for the sched class to which the instr belongs.
433     choiceVec.push_back(node);
434     const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpCode());
435     assert(sc < (int) numInClass.size());
436     numInClass[sc]++;
437   }
438   
439   inline void   addChoiceToSlot         (unsigned int slotNum,
440                                          const SchedGraphNode* node) {
441     // Add the instruction to the choice set for the specified slot
442     assert(slotNum < nslots);
443     choicesForSlot[slotNum].insert(node);
444   }
445   
446   inline void   resetChoices            () {
447     choiceVec.clear();
448     for (unsigned int s=0; s < nslots; s++)
449       choicesForSlot[s].clear();
450     for (unsigned int c=0; c < numInClass.size(); c++)
451       numInClass[c] = 0;
452   }
453   
454   //----------------------------------------------------------------------
455   // Code to query and manage the partial instruction schedule so far
456   //----------------------------------------------------------------------
457   
458   inline unsigned int   getNumScheduled () const {
459     return isched.getNumInstructions();
460   }
461   
462   inline unsigned int   getNumUnscheduled() const {
463     return totalInstrCount - isched.getNumInstructions();
464   }
465   
466   inline bool           isScheduled     (const SchedGraphNode* node) const {
467     return (isched.getStartTime(node->getNodeId()) >= 0);
468   }
469   
470   inline void   scheduleInstr           (const SchedGraphNode* node,
471                                          unsigned int slotNum,
472                                          cycles_t cycle)
473   {
474     assert(! isScheduled(node) && "Instruction already scheduled?");
475     
476     // add the instruction to the schedule
477     isched.scheduleInstr(node, slotNum, cycle);
478     
479     // update the earliest start times of all nodes that conflict with `node'
480     // and the next-earliest time anything can issue if `node' causes bubbles
481     updateEarliestStartTimes(node, cycle);
482     
483     // remove the instruction from the choice sets for all slots
484     for (unsigned s=0; s < nslots; s++)
485       choicesForSlot[s].erase(node);
486     
487     // and decrement the instr count for the sched class to which it belongs
488     const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpCode());
489     assert(sc < (int) numInClass.size());
490     numInClass[sc]--;
491   }
492
493   //----------------------------------------------------------------------
494   // Create and retrieve delay slot info for delayed instructions
495   //----------------------------------------------------------------------
496   
497   inline DelaySlotInfo* getDelaySlotInfoForInstr(const SchedGraphNode* bn,
498                                                  bool createIfMissing=false)
499   {
500     hash_map<const SchedGraphNode*, DelaySlotInfo*>::const_iterator
501       I = delaySlotInfoForBranches.find(bn);
502     if (I != delaySlotInfoForBranches.end())
503       return I->second;
504
505     if (!createIfMissing) return 0;
506
507     DelaySlotInfo *dinfo =
508       new DelaySlotInfo(bn, getInstrInfo().getNumDelaySlots(bn->getOpCode()));
509     return delaySlotInfoForBranches[bn] = dinfo;
510   }
511   
512 private:
513   SchedulingManager();     // DISABLED: DO NOT IMPLEMENT
514   void updateEarliestStartTimes(const SchedGraphNode* node, cycles_t schedTime);
515 };
516
517
518 /*ctor*/
519 SchedulingManager::SchedulingManager(const TargetMachine& target,
520                                      const SchedGraph* graph,
521                                      SchedPriorities& _schedPrio)
522   : nslots(target.getSchedInfo().getMaxNumIssueTotal()),
523     schedInfo(target.getSchedInfo()),
524     schedPrio(_schedPrio),
525     isched(nslots, graph->getNumNodes()),
526     totalInstrCount(graph->getNumNodes() - 2),
527     nextEarliestIssueTime(0),
528     choicesForSlot(nslots),
529     numInClass(target.getSchedInfo().getNumSchedClasses(), 0),  // set all to 0
530     nextEarliestStartTime(target.getInstrInfo().getNumRealOpCodes(),
531                           (cycles_t) 0)                         // set all to 0
532 {
533   updateTime(0);
534   
535   // Note that an upper bound on #choices for each slot is = nslots since
536   // we use this vector to hold a feasible set of instructions, and more
537   // would be infeasible. Reserve that much memory since it is probably small.
538   for (unsigned int i=0; i < nslots; i++)
539     choicesForSlot[i].resize(nslots);
540 }
541
542
543 void
544 SchedulingManager::updateEarliestStartTimes(const SchedGraphNode* node,
545                                             cycles_t schedTime)
546 {
547   if (schedInfo.numBubblesAfter(node->getOpCode()) > 0)
548     { // Update next earliest time before which *nothing* can issue.
549       nextEarliestIssueTime = std::max(nextEarliestIssueTime,
550                   curTime + 1 + schedInfo.numBubblesAfter(node->getOpCode()));
551     }
552   
553   const vector<MachineOpCode>*
554     conflictVec = schedInfo.getConflictList(node->getOpCode());
555   
556   if (conflictVec != NULL)
557     for (unsigned i=0; i < conflictVec->size(); i++)
558       {
559         MachineOpCode toOp = (*conflictVec)[i];
560         cycles_t est = schedTime + schedInfo.getMinIssueGap(node->getOpCode(),
561                                                             toOp);
562         assert(toOp < (int) nextEarliestStartTime.size());
563         if (nextEarliestStartTime[toOp] < est)
564           nextEarliestStartTime[toOp] = est;
565       }
566 }
567
568 //************************* Internal Functions *****************************/
569
570
571 static void
572 AssignInstructionsToSlots(class SchedulingManager& S, unsigned maxIssue)
573 {
574   // find the slot to start from, in the current cycle
575   unsigned int startSlot = 0;
576   cycles_t curTime = S.getTime();
577   
578   assert(maxIssue > 0 && maxIssue <= S.nslots - startSlot);
579   
580   // If only one instruction can be issued, do so.
581   if (maxIssue == 1)
582     for (unsigned s=startSlot; s < S.nslots; s++)
583       if (S.getChoicesForSlot(s).size() > 0)
584         {// found the one instruction
585           S.scheduleInstr(*S.getChoicesForSlot(s).begin(), s, curTime);
586           return;
587         }
588   
589   // Otherwise, choose from the choices for each slot
590   // 
591   InstrGroup* igroup = S.isched.getIGroup(S.getTime());
592   assert(igroup != NULL && "Group creation failed?");
593   
594   // Find a slot that has only a single choice, and take it.
595   // If all slots have 0 or multiple choices, pick the first slot with
596   // choices and use its last instruction (just to avoid shifting the vector).
597   unsigned numIssued;
598   for (numIssued = 0; numIssued < maxIssue; numIssued++)
599     {
600       int chosenSlot = -1;
601       for (unsigned s=startSlot; s < S.nslots; s++)
602         if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() == 1)
603           {
604             chosenSlot = (int) s;
605             break;
606           }
607       
608       if (chosenSlot == -1)
609         for (unsigned s=startSlot; s < S.nslots; s++)
610           if ((*igroup)[s] == NULL && S.getChoicesForSlot(s).size() > 0)
611             {
612               chosenSlot = (int) s;
613               break;
614             }
615       
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);
621         }
622     }
623   
624   assert(numIssued > 0 && "Should not happen when maxIssue > 0!");
625 }
626
627
628 // 
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.
634 //   
635 static void
636 RecordSchedule(const BasicBlock* bb, const SchedulingManager& S)
637 {
638   MachineCodeForBasicBlock& mvec = MachineCodeForBasicBlock::get(bb);
639   const MachineInstrInfo& mii = S.schedInfo.getInstrInfo();
640   
641 #ifndef NDEBUG
642   // Lets make sure we didn't lose any instructions, except possibly
643   // some NOPs from delay slots.  Also, PHIs are not included in the schedule.
644   unsigned numInstr = 0;
645   for (MachineCodeForBasicBlock::iterator I=mvec.begin(); I != mvec.end(); ++I)
646     if (! mii.isNop((*I)->getOpCode()) &&
647         ! mii.isDummyPhiInstr((*I)->getOpCode()))
648       ++numInstr;
649   assert(S.isched.getNumInstructions() >= numInstr &&
650          "Lost some non-NOP instructions during scheduling!");
651 #endif
652   
653   if (S.isched.getNumInstructions() == 0)
654     return;                             // empty basic block!
655   
656   // First find the dummy instructions at the start of the basic block
657   MachineCodeForBasicBlock::iterator I = mvec.begin();
658   for ( ; I != mvec.end(); ++I)
659     if (! mii.isDummyPhiInstr((*I)->getOpCode()))
660       break;
661   
662   // Erase all except the dummy PHI instructions from mvec, and
663   // pre-allocate create space for the ones we will put back in.
664   mvec.erase(I, mvec.end());
665   
666   InstrSchedule::const_iterator NIend = S.isched.end();
667   for (InstrSchedule::const_iterator NI = S.isched.begin(); NI != NIend; ++NI)
668     mvec.push_back(const_cast<MachineInstr*>((*NI)->getMachineInstr()));
669 }
670
671
672
673 static void
674 MarkSuccessorsReady(SchedulingManager& S, const SchedGraphNode* node)
675 {
676   // Check if any successors are now ready that were not already marked
677   // ready before, and that have not yet been scheduled.
678   // 
679   for (sg_succ_const_iterator SI = succ_begin(node); SI !=succ_end(node); ++SI)
680     if (! (*SI)->isDummyNode()
681         && ! S.isScheduled(*SI)
682         && ! S.schedPrio.nodeIsReady(*SI))
683       {// successor not scheduled and not marked ready; check *its* preds.
684         
685         bool succIsReady = true;
686         for (sg_pred_const_iterator P=pred_begin(*SI); P != pred_end(*SI); ++P)
687           if (! (*P)->isDummyNode()
688               && ! S.isScheduled(*P))
689             {
690               succIsReady = false;
691               break;
692             }
693         
694         if (succIsReady)        // add the successor to the ready list
695           S.schedPrio.insertReady(*SI);
696       }
697 }
698
699
700 // Choose up to `nslots' FEASIBLE instructions and assign each
701 // instruction to all possible slots that do not violate feasibility.
702 // FEASIBLE means it should be guaranteed that the set
703 // of chosen instructions can be issued in a single group.
704 // 
705 // Return value:
706 //      maxIssue : total number of feasible instructions
707 //      S.choicesForSlot[i=0..nslots] : set of instructions feasible in slot i
708 // 
709 static unsigned
710 FindSlotChoices(SchedulingManager& S,
711                 DelaySlotInfo*& getDelaySlotInfo)
712 {
713   // initialize result vectors to empty
714   S.resetChoices();
715   
716   // find the slot to start from, in the current cycle
717   unsigned int startSlot = 0;
718   InstrGroup* igroup = S.isched.getIGroup(S.getTime());
719   for (int s = S.nslots - 1; s >= 0; s--)
720     if ((*igroup)[s] != NULL)
721       {
722         startSlot = s+1;
723         break;
724       }
725   
726   // Make sure we pick at most one instruction that would break the group.
727   // Also, if we do pick one, remember which it was.
728   unsigned int indexForBreakingNode = S.nslots;
729   unsigned int indexForDelayedInstr = S.nslots;
730   DelaySlotInfo* delaySlotInfo = NULL;
731
732   getDelaySlotInfo = NULL;
733   
734   // Choose instructions in order of priority.
735   // Add choices to the choice vector in the SchedulingManager class as
736   // we choose them so that subsequent choices will be correctly tested
737   // for feasibility, w.r.t. higher priority choices for the same cycle.
738   // 
739   while (S.getNumChoices() < S.nslots - startSlot)
740     {
741       const SchedGraphNode* nextNode=S.schedPrio.getNextHighest(S,S.getTime());
742       if (nextNode == NULL)
743         break;                  // no more instructions for this cycle
744       
745       if (S.getInstrInfo().getNumDelaySlots(nextNode->getOpCode()) > 0)
746         {
747           delaySlotInfo = S.getDelaySlotInfoForInstr(nextNode);
748           if (delaySlotInfo != NULL)
749             {
750               if (indexForBreakingNode < S.nslots)
751                 // cannot issue a delayed instr in the same cycle as one
752                 // that breaks the issue group or as another delayed instr
753                 nextNode = NULL;
754               else
755                 indexForDelayedInstr = S.getNumChoices();
756             }
757         }
758       else if (S.schedInfo.breaksIssueGroup(nextNode->getOpCode()))
759         {
760           if (indexForBreakingNode < S.nslots)
761             // have a breaking instruction already so throw this one away
762             nextNode = NULL;
763           else
764             indexForBreakingNode = S.getNumChoices();
765         }
766       
767       if (nextNode != NULL)
768         {
769           S.addChoice(nextNode);
770       
771           if (S.schedInfo.isSingleIssue(nextNode->getOpCode()))
772             {
773               assert(S.getNumChoices() == 1 &&
774                      "Prioritizer returned invalid instr for this cycle!");
775               break;
776             }
777         }
778           
779       if (indexForDelayedInstr < S.nslots)
780         break;                  // leave the rest for delay slots
781     }
782   
783   assert(S.getNumChoices() <= S.nslots);
784   assert(! (indexForDelayedInstr < S.nslots &&
785             indexForBreakingNode < S.nslots) && "Cannot have both in a cycle");
786   
787   // Assign each chosen instruction to all possible slots for that instr.
788   // But if only one instruction was chosen, put it only in the first
789   // feasible slot; no more analysis will be needed.
790   // 
791   if (indexForDelayedInstr >= S.nslots && 
792       indexForBreakingNode >= S.nslots)
793     { // No instructions that break the issue group or that have delay slots.
794       // This is the common case, so handle it separately for efficiency.
795       
796       if (S.getNumChoices() == 1)
797         {
798           MachineOpCode opCode = S.getChoice(0)->getOpCode();
799           unsigned int s;
800           for (s=startSlot; s < S.nslots; s++)
801             if (S.schedInfo.instrCanUseSlot(opCode, s))
802               break;
803           assert(s < S.nslots && "No feasible slot for this opCode?");
804           S.addChoiceToSlot(s, S.getChoice(0));
805         }
806       else
807         {
808           for (unsigned i=0; i < S.getNumChoices(); i++)
809             {
810               MachineOpCode opCode = S.getChoice(i)->getOpCode();
811               for (unsigned int s=startSlot; s < S.nslots; s++)
812                 if (S.schedInfo.instrCanUseSlot(opCode, s))
813                   S.addChoiceToSlot(s, S.getChoice(i));
814             }
815         }
816     }
817   else if (indexForDelayedInstr < S.nslots)
818     {
819       // There is an instruction that needs delay slots.
820       // Try to assign that instruction to a higher slot than any other
821       // instructions in the group, so that its delay slots can go
822       // right after it.
823       //  
824
825       assert(indexForDelayedInstr == S.getNumChoices() - 1 &&
826              "Instruction with delay slots should be last choice!");
827       assert(delaySlotInfo != NULL && "No delay slot info for instr?");
828       
829       const SchedGraphNode* delayedNode = S.getChoice(indexForDelayedInstr);
830       MachineOpCode delayOpCode = delayedNode->getOpCode();
831       unsigned ndelays= S.getInstrInfo().getNumDelaySlots(delayOpCode);
832       
833       unsigned delayedNodeSlot = S.nslots;
834       int highestSlotUsed;
835       
836       // Find the last possible slot for the delayed instruction that leaves
837       // at least `d' slots vacant after it (d = #delay slots)
838       for (int s = S.nslots-ndelays-1; s >= (int) startSlot; s--)
839         if (S.schedInfo.instrCanUseSlot(delayOpCode, s))
840           {
841             delayedNodeSlot = s;
842             break;
843           }
844       
845       highestSlotUsed = -1;
846       for (unsigned i=0; i < S.getNumChoices() - 1; i++)
847         {
848           // Try to assign every other instruction to a lower numbered
849           // slot than delayedNodeSlot.
850           MachineOpCode opCode =S.getChoice(i)->getOpCode();
851           bool noSlotFound = true;
852           unsigned int s;
853           for (s=startSlot; s < delayedNodeSlot; s++)
854             if (S.schedInfo.instrCanUseSlot(opCode, s))
855               {
856                 S.addChoiceToSlot(s, S.getChoice(i));
857                 noSlotFound = false;
858               }
859           
860           // No slot before `delayedNodeSlot' was found for this opCode
861           // Use a later slot, and allow some delay slots to fall in
862           // the next cycle.
863           if (noSlotFound)
864             for ( ; s < S.nslots; s++)
865               if (S.schedInfo.instrCanUseSlot(opCode, s))
866                 {
867                   S.addChoiceToSlot(s, S.getChoice(i));
868                   break;
869                 }
870           
871           assert(s < S.nslots && "No feasible slot for instruction?");
872           
873           highestSlotUsed = std::max(highestSlotUsed, (int) s);
874         }
875       
876       assert(highestSlotUsed <= (int) S.nslots-1 && "Invalid slot used?");
877       
878       // We will put the delayed node in the first slot after the
879       // highest slot used.  But we just mark that for now, and
880       // schedule it separately because we want to schedule the delay
881       // slots for the node at the same time.
882       cycles_t dcycle = S.getTime();
883       unsigned int dslot = highestSlotUsed + 1;
884       if (dslot == S.nslots)
885         {
886           dslot = 0;
887           ++dcycle;
888         }
889       delaySlotInfo->recordChosenSlot(dcycle, dslot);
890       getDelaySlotInfo = delaySlotInfo;
891     }
892   else
893     { // There is an instruction that breaks the issue group.
894       // For such an instruction, assign to the last possible slot in
895       // the current group, and then don't assign any other instructions
896       // to later slots.
897       assert(indexForBreakingNode < S.nslots);
898       const SchedGraphNode* breakingNode=S.getChoice(indexForBreakingNode);
899       unsigned breakingSlot = INT_MAX;
900       unsigned int nslotsToUse = S.nslots;
901           
902       // Find the last possible slot for this instruction.
903       for (int s = S.nslots-1; s >= (int) startSlot; s--)
904         if (S.schedInfo.instrCanUseSlot(breakingNode->getOpCode(), s))
905           {
906             breakingSlot = s;
907             break;
908           }
909       assert(breakingSlot < S.nslots &&
910              "No feasible slot for `breakingNode'?");
911       
912       // Higher priority instructions than the one that breaks the group:
913       // These can be assigned to all slots, but will be assigned only
914       // to earlier slots if possible.
915       for (unsigned i=0;
916            i < S.getNumChoices() && i < indexForBreakingNode; i++)
917         {
918           MachineOpCode opCode =S.getChoice(i)->getOpCode();
919           
920           // If a higher priority instruction cannot be assigned to
921           // any earlier slots, don't schedule the breaking instruction.
922           // 
923           bool foundLowerSlot = false;
924           nslotsToUse = S.nslots;           // May be modified in the loop
925           for (unsigned int s=startSlot; s < nslotsToUse; s++)
926             if (S.schedInfo.instrCanUseSlot(opCode, s))
927               {
928                 if (breakingSlot < S.nslots && s < breakingSlot)
929                   {
930                     foundLowerSlot = true;
931                     nslotsToUse = breakingSlot; // RESETS LOOP UPPER BOUND!
932                   }
933                     
934                 S.addChoiceToSlot(s, S.getChoice(i));
935               }
936               
937           if (!foundLowerSlot)
938             breakingSlot = INT_MAX;             // disable breaking instr
939         }
940       
941       // Assign the breaking instruction (if any) to a single slot
942       // Otherwise, just ignore the instruction.  It will simply be
943       // scheduled in a later cycle.
944       if (breakingSlot < S.nslots)
945         {
946           S.addChoiceToSlot(breakingSlot, breakingNode);
947           nslotsToUse = breakingSlot;
948         }
949       else
950         nslotsToUse = S.nslots;
951           
952       // For lower priority instructions than the one that breaks the
953       // group, only assign them to slots lower than the breaking slot.
954       // Otherwise, just ignore the instruction.
955       for (unsigned i=indexForBreakingNode+1; i < S.getNumChoices(); i++)
956         {
957           MachineOpCode opCode = S.getChoice(i)->getOpCode();
958           for (unsigned int s=startSlot; s < nslotsToUse; s++)
959             if (S.schedInfo.instrCanUseSlot(opCode, s))
960               S.addChoiceToSlot(s, S.getChoice(i));
961         }
962     } // endif (no delay slots and no breaking slots)
963   
964   return S.getNumChoices();
965 }
966
967
968 static unsigned
969 ChooseOneGroup(SchedulingManager& S)
970 {
971   assert(S.schedPrio.getNumReady() > 0
972          && "Don't get here without ready instructions.");
973   
974   cycles_t firstCycle = S.getTime();
975   DelaySlotInfo* getDelaySlotInfo = NULL;
976   
977   // Choose up to `nslots' feasible instructions and their possible slots.
978   unsigned numIssued = FindSlotChoices(S, getDelaySlotInfo);
979   
980   while (numIssued == 0)
981     {
982       S.updateTime(S.getTime()+1);
983       numIssued = FindSlotChoices(S, getDelaySlotInfo);
984     }
985   
986   AssignInstructionsToSlots(S, numIssued);
987   
988   if (getDelaySlotInfo != NULL)
989     numIssued += getDelaySlotInfo->scheduleDelayedNode(S); 
990   
991   // Print trace of scheduled instructions before newly ready ones
992   if (SchedDebugLevel >= Sched_PrintSchedTrace)
993     {
994       for (cycles_t c = firstCycle; c <= S.getTime(); c++)
995         {
996           cerr << "    Cycle " << (long)c << " : Scheduled instructions:\n";
997           const InstrGroup* igroup = S.isched.getIGroup(c);
998           for (unsigned int s=0; s < S.nslots; s++)
999             {
1000               cerr << "        ";
1001               if ((*igroup)[s] != NULL)
1002                 cerr << * ((*igroup)[s])->getMachineInstr() << "\n";
1003               else
1004                 cerr << "<none>\n";
1005             }
1006         }
1007     }
1008   
1009   return numIssued;
1010 }
1011
1012
1013 static void
1014 ForwardListSchedule(SchedulingManager& S)
1015 {
1016   unsigned N;
1017   const SchedGraphNode* node;
1018   
1019   S.schedPrio.initialize();
1020   
1021   while ((N = S.schedPrio.getNumReady()) > 0)
1022     {
1023       cycles_t nextCycle = S.getTime();
1024       
1025       // Choose one group of instructions for a cycle, plus any delay slot
1026       // instructions (which may overflow into successive cycles).
1027       // This will advance S.getTime() to the last cycle in which
1028       // instructions are actually issued.
1029       // 
1030       unsigned numIssued = ChooseOneGroup(S);
1031       assert(numIssued > 0 && "Deadlock in list scheduling algorithm?");
1032       
1033       // Notify the priority manager of scheduled instructions and mark
1034       // any successors that may now be ready
1035       // 
1036       for (cycles_t c = nextCycle; c <= S.getTime(); c++)
1037         {
1038           const InstrGroup* igroup = S.isched.getIGroup(c);
1039           for (unsigned int s=0; s < S.nslots; s++)
1040             if ((node = (*igroup)[s]) != NULL)
1041               {
1042                 S.schedPrio.issuedReadyNodeAt(S.getTime(), node);
1043                 MarkSuccessorsReady(S, node);
1044               }
1045         }
1046       
1047       // Move to the next the next earliest cycle for which
1048       // an instruction can be issued, or the next earliest in which
1049       // one will be ready, or to the next cycle, whichever is latest.
1050       // 
1051       S.updateTime(std::max(S.getTime() + 1,
1052                             std::max(S.getEarliestIssueTime(),
1053                                      S.schedPrio.getEarliestReadyTime())));
1054     }
1055 }
1056
1057
1058 //---------------------------------------------------------------------
1059 // Code for filling delay slots for delayed terminator instructions
1060 // (e.g., BRANCH and RETURN).  Delay slots for non-terminator
1061 // instructions (e.g., CALL) are not handled here because they almost
1062 // always can be filled with instructions from the call sequence code
1063 // before a call.  That's preferable because we incur many tradeoffs here
1064 // when we cannot find single-cycle instructions that can be reordered.
1065 //----------------------------------------------------------------------
1066
1067 static bool
1068 NodeCanFillDelaySlot(const SchedulingManager& S,
1069                      const SchedGraphNode* node,
1070                      const SchedGraphNode* brNode,
1071                      bool nodeIsPredecessor)
1072 {
1073   assert(! node->isDummyNode());
1074   
1075   // don't put a branch in the delay slot of another branch
1076   if (S.getInstrInfo().isBranch(node->getOpCode()))
1077     return false;
1078   
1079   // don't put a single-issue instruction in the delay slot of a branch
1080   if (S.schedInfo.isSingleIssue(node->getOpCode()))
1081     return false;
1082   
1083   // don't put a load-use dependence in the delay slot of a branch
1084   const MachineInstrInfo& mii = S.getInstrInfo();
1085   
1086   for (SchedGraphNode::const_iterator EI = node->beginInEdges();
1087        EI != node->endInEdges(); ++EI)
1088     if (! (*EI)->getSrc()->isDummyNode()
1089         && mii.isLoad((*EI)->getSrc()->getOpCode())
1090         && (*EI)->getDepType() == SchedGraphEdge::CtrlDep)
1091       return false;
1092   
1093   // for now, don't put an instruction that does not have operand
1094   // interlocks in the delay slot of a branch
1095   if (! S.getInstrInfo().hasOperandInterlock(node->getOpCode()))
1096     return false;
1097   
1098   // Finally, if the instruction preceeds the branch, we make sure the
1099   // instruction can be reordered relative to the branch.  We simply check
1100   // if the instr. has only 1 outgoing edge, viz., a CD edge to the branch.
1101   // 
1102   if (nodeIsPredecessor)
1103     {
1104       bool onlyCDEdgeToBranch = true;
1105       for (SchedGraphNode::const_iterator OEI = node->beginOutEdges();
1106            OEI != node->endOutEdges(); ++OEI)
1107         if (! (*OEI)->getSink()->isDummyNode()
1108             && ((*OEI)->getSink() != brNode
1109                 || (*OEI)->getDepType() != SchedGraphEdge::CtrlDep))
1110           {
1111             onlyCDEdgeToBranch = false;
1112             break;
1113           }
1114       
1115       if (!onlyCDEdgeToBranch)
1116         return false;
1117     }
1118   
1119   return true;
1120 }
1121
1122
1123 static void
1124 MarkNodeForDelaySlot(SchedulingManager& S,
1125                      SchedGraph* graph,
1126                      SchedGraphNode* node,
1127                      const SchedGraphNode* brNode,
1128                      bool nodeIsPredecessor)
1129 {
1130   if (nodeIsPredecessor)
1131     { // If node is in the same basic block (i.e., preceeds brNode),
1132       // remove it and all its incident edges from the graph.  Make sure we
1133       // add dummy edges for pred/succ nodes that become entry/exit nodes.
1134       graph->eraseIncidentEdges(node, /*addDummyEdges*/ true);
1135     }
1136   else
1137     { // If the node was from a target block, add the node to the graph
1138       // and add a CD edge from brNode to node.
1139       assert(0 && "NOT IMPLEMENTED YET");
1140     }
1141   
1142   DelaySlotInfo* dinfo = S.getDelaySlotInfoForInstr(brNode, /*create*/ true);
1143   dinfo->addDelayNode(node);
1144 }
1145
1146
1147 void
1148 FindUsefulInstructionsForDelaySlots(SchedulingManager& S,
1149                                     SchedGraphNode* brNode,
1150                                     vector<SchedGraphNode*>& sdelayNodeVec)
1151 {
1152   const MachineInstrInfo& mii = S.getInstrInfo();
1153   unsigned ndelays =
1154     mii.getNumDelaySlots(brNode->getOpCode());
1155   
1156   if (ndelays == 0)
1157     return;
1158   
1159   sdelayNodeVec.reserve(ndelays);
1160   
1161   // Use a separate vector to hold the feasible multi-cycle nodes.
1162   // These will be used if not enough single-cycle nodes are found.
1163   // 
1164   vector<SchedGraphNode*> mdelayNodeVec;
1165   
1166   for (sg_pred_iterator P = pred_begin(brNode);
1167        P != pred_end(brNode) && sdelayNodeVec.size() < ndelays; ++P)
1168     if (! (*P)->isDummyNode() &&
1169         ! mii.isNop((*P)->getOpCode()) &&
1170         NodeCanFillDelaySlot(S, *P, brNode, /*pred*/ true))
1171       {
1172         if (mii.maxLatency((*P)->getOpCode()) > 1)
1173           mdelayNodeVec.push_back(*P);
1174         else
1175           sdelayNodeVec.push_back(*P);
1176       }
1177   
1178   // If not enough single-cycle instructions were found, select the
1179   // lowest-latency multi-cycle instructions and use them.
1180   // Note that this is the most efficient code when only 1 (or even 2)
1181   // values need to be selected.
1182   // 
1183   while (sdelayNodeVec.size() < ndelays && mdelayNodeVec.size() > 0)
1184     {
1185       unsigned lmin =
1186         mii.maxLatency(mdelayNodeVec[0]->getOpCode());
1187       unsigned minIndex   = 0;
1188       for (unsigned i=1; i < mdelayNodeVec.size(); i++)
1189         {
1190           unsigned li = 
1191             mii.maxLatency(mdelayNodeVec[i]->getOpCode());
1192           if (lmin >= li)
1193             {
1194               lmin = li;
1195               minIndex = i;
1196             }
1197         }
1198       sdelayNodeVec.push_back(mdelayNodeVec[minIndex]);
1199       if (sdelayNodeVec.size() < ndelays) // avoid the last erase!
1200         mdelayNodeVec.erase(mdelayNodeVec.begin() + minIndex);
1201     }
1202 }
1203
1204
1205 // Remove the NOPs currently in delay slots from the graph.
1206 // Mark instructions specified in sdelayNodeVec to replace them.
1207 // If not enough useful instructions were found, mark the NOPs to be used
1208 // for filling delay slots, otherwise, otherwise just discard them.
1209 // 
1210 void
1211 ReplaceNopsWithUsefulInstr(SchedulingManager& S,
1212                            SchedGraphNode* node,
1213                            vector<SchedGraphNode*> sdelayNodeVec,
1214                            SchedGraph* graph)
1215 {
1216   vector<SchedGraphNode*> nopNodeVec;   // this will hold unused NOPs
1217   const MachineInstrInfo& mii = S.getInstrInfo();
1218   const MachineInstr* brInstr = node->getMachineInstr();
1219   unsigned ndelays= mii.getNumDelaySlots(brInstr->getOpCode());
1220   assert(ndelays > 0 && "Unnecessary call to replace NOPs");
1221   
1222   // Remove the NOPs currently in delay slots from the graph.
1223   // If not enough useful instructions were found, use the NOPs to
1224   // fill delay slots, otherwise, just discard them.
1225   //  
1226   unsigned int firstDelaySlotIdx = node->getOrigIndexInBB() + 1;
1227   MachineCodeForBasicBlock& bbMvec = MachineCodeForBasicBlock::get(node->getBB());
1228   assert(bbMvec[firstDelaySlotIdx - 1] == brInstr &&
1229          "Incorrect instr. index in basic block for brInstr");
1230   
1231   // First find all useful instructions already in the delay slots
1232   // and USE THEM.  We'll throw away the unused alternatives below
1233   // 
1234   for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
1235     if (! mii.isNop(bbMvec[i]->getOpCode()))
1236       sdelayNodeVec.insert(sdelayNodeVec.begin(),
1237                            graph->getGraphNodeForInstr(bbMvec[i]));
1238   
1239   // Then find the NOPs and keep only as many as are needed.
1240   // Put the rest in nopNodeVec to be deleted.
1241   for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
1242     if (mii.isNop(bbMvec[i]->getOpCode()))
1243       if (sdelayNodeVec.size() < ndelays)
1244         sdelayNodeVec.push_back(graph->getGraphNodeForInstr(bbMvec[i]));
1245       else
1246         {
1247           nopNodeVec.push_back(graph->getGraphNodeForInstr(bbMvec[i]));
1248           
1249           //remove the MI from the Machine Code For Instruction
1250           MachineCodeForInstruction& llvmMvec = 
1251             MachineCodeForInstruction::get((Instruction *)
1252                                            (node->getBB()->getTerminator()));
1253           for(MachineCodeForInstruction::iterator mciI=llvmMvec.begin(), 
1254                 mciE=llvmMvec.end(); mciI!=mciE; ++mciI){
1255             if(*mciI==bbMvec[i])
1256               llvmMvec.erase(mciI);
1257           }
1258         }
1259
1260   assert(sdelayNodeVec.size() >= ndelays);
1261   
1262   // If some delay slots were already filled, throw away that many new choices
1263   if (sdelayNodeVec.size() > ndelays)
1264     sdelayNodeVec.resize(ndelays);
1265   
1266   // Mark the nodes chosen for delay slots.  This removes them from the graph.
1267   for (unsigned i=0; i < sdelayNodeVec.size(); i++)
1268     MarkNodeForDelaySlot(S, graph, sdelayNodeVec[i], node, true);
1269   
1270   // And remove the unused NOPs from the graph.
1271   for (unsigned i=0; i < nopNodeVec.size(); i++)
1272     graph->eraseIncidentEdges(nopNodeVec[i], /*addDummyEdges*/ true);
1273 }
1274
1275
1276 // For all delayed instructions, choose instructions to put in the delay
1277 // slots and pull those out of the graph.  Mark them for the delay slots
1278 // in the DelaySlotInfo object for that graph node.  If no useful work
1279 // is found for a delay slot, use the NOP that is currently in that slot.
1280 // 
1281 // We try to fill the delay slots with useful work for all instructions
1282 // EXCEPT CALLS AND RETURNS.
1283 // For CALLs and RETURNs, it is nearly always possible to use one of the
1284 // call sequence instrs and putting anything else in the delay slot could be
1285 // suboptimal.  Also, it complicates generating the calling sequence code in
1286 // regalloc.
1287 // 
1288 static void
1289 ChooseInstructionsForDelaySlots(SchedulingManager& S,
1290                                 const BasicBlock *bb,
1291                                 SchedGraph *graph)
1292 {
1293   const MachineInstrInfo& mii = S.getInstrInfo();
1294   const Instruction *termInstr = (Instruction*)bb->getTerminator();
1295   MachineCodeForInstruction &termMvec=MachineCodeForInstruction::get(termInstr);
1296   vector<SchedGraphNode*> delayNodeVec;
1297   const MachineInstr* brInstr = NULL;
1298   
1299   if (termInstr->getOpcode() != Instruction::Ret)
1300     {
1301       // To find instructions that need delay slots without searching the full
1302       // machine code, we assume that the only delayed instructions are CALLs
1303       // or instructions generated for the terminator inst.
1304       // Find the first branch instr in the sequence of machine instrs for term
1305       // 
1306       unsigned first = 0;
1307       while (first < termMvec.size() &&
1308              ! mii.isBranch(termMvec[first]->getOpCode()))
1309         {
1310           ++first;
1311         }
1312       assert(first < termMvec.size() &&
1313          "No branch instructions for BR?  Ok, but weird!  Delete assertion.");
1314       
1315       brInstr = (first < termMvec.size())? termMvec[first] : NULL;
1316       
1317       // Compute a vector of the nodes chosen for delay slots and then
1318       // mark delay slots to replace NOPs with these useful instructions.
1319       // 
1320       if (brInstr != NULL)
1321         {
1322           SchedGraphNode* brNode = graph->getGraphNodeForInstr(brInstr);
1323           FindUsefulInstructionsForDelaySlots(S, brNode, delayNodeVec);
1324           ReplaceNopsWithUsefulInstr(S, brNode, delayNodeVec, graph);
1325         }
1326     }
1327   
1328   // Also mark delay slots for other delayed instructions to hold NOPs. 
1329   // Simply passing in an empty delayNodeVec will have this effect.
1330   // 
1331   delayNodeVec.clear();
1332   const MachineCodeForBasicBlock& bbMvec = MachineCodeForBasicBlock::get(bb);
1333   for (unsigned i=0; i < bbMvec.size(); i++)
1334     if (bbMvec[i] != brInstr &&
1335         mii.getNumDelaySlots(bbMvec[i]->getOpCode()) > 0)
1336       {
1337         SchedGraphNode* node = graph->getGraphNodeForInstr(bbMvec[i]);
1338         ReplaceNopsWithUsefulInstr(S, node, delayNodeVec, graph);
1339       }
1340 }
1341
1342
1343 // 
1344 // Schedule the delayed branch and its delay slots
1345 // 
1346 unsigned
1347 DelaySlotInfo::scheduleDelayedNode(SchedulingManager& S)
1348 {
1349   assert(delayedNodeSlotNum < S.nslots && "Illegal slot for branch");
1350   assert(S.isched.getInstr(delayedNodeSlotNum, delayedNodeCycle) == NULL
1351          && "Slot for branch should be empty");
1352   
1353   unsigned int nextSlot = delayedNodeSlotNum;
1354   cycles_t nextTime = delayedNodeCycle;
1355   
1356   S.scheduleInstr(brNode, nextSlot, nextTime);
1357   
1358   for (unsigned d=0; d < ndelays; d++)
1359     {
1360       ++nextSlot;
1361       if (nextSlot == S.nslots)
1362         {
1363           nextSlot = 0;
1364           nextTime++;
1365         }
1366       
1367       // Find the first feasible instruction for this delay slot
1368       // Note that we only check for issue restrictions here.
1369       // We do *not* check for flow dependences but rely on pipeline
1370       // interlocks to resolve them.  Machines without interlocks
1371       // will require this code to be modified.
1372       for (unsigned i=0; i < delayNodeVec.size(); i++)
1373         {
1374           const SchedGraphNode* dnode = delayNodeVec[i];
1375           if ( ! S.isScheduled(dnode)
1376                && S.schedInfo.instrCanUseSlot(dnode->getOpCode(), nextSlot)
1377                && instrIsFeasible(S, dnode->getOpCode()))
1378             {
1379               assert(S.getInstrInfo().hasOperandInterlock(dnode->getOpCode())
1380                      && "Instructions without interlocks not yet supported "
1381                      "when filling branch delay slots");
1382               S.scheduleInstr(dnode, nextSlot, nextTime);
1383               break;
1384             }
1385         }
1386     }
1387   
1388   // Update current time if delay slots overflowed into later cycles.
1389   // Do this here because we know exactly which cycle is the last cycle
1390   // that contains delay slots.  The next loop doesn't compute that.
1391   if (nextTime > S.getTime())
1392     S.updateTime(nextTime);
1393   
1394   // Now put any remaining instructions in the unfilled delay slots.
1395   // This could lead to suboptimal performance but needed for correctness.
1396   nextSlot = delayedNodeSlotNum;
1397   nextTime = delayedNodeCycle;
1398   for (unsigned i=0; i < delayNodeVec.size(); i++)
1399     if (! S.isScheduled(delayNodeVec[i]))
1400       {
1401         do { // find the next empty slot
1402           ++nextSlot;
1403           if (nextSlot == S.nslots)
1404             {
1405               nextSlot = 0;
1406               nextTime++;
1407             }
1408         } while (S.isched.getInstr(nextSlot, nextTime) != NULL);
1409         
1410         S.scheduleInstr(delayNodeVec[i], nextSlot, nextTime);
1411         break;
1412       }
1413
1414   return 1 + ndelays;
1415 }
1416
1417
1418 // Check if the instruction would conflict with instructions already
1419 // chosen for the current cycle
1420 // 
1421 static inline bool
1422 ConflictsWithChoices(const SchedulingManager& S,
1423                      MachineOpCode opCode)
1424 {
1425   // Check if the instruction must issue by itself, and some feasible
1426   // choices have already been made for this cycle
1427   if (S.getNumChoices() > 0 && S.schedInfo.isSingleIssue(opCode))
1428     return true;
1429   
1430   // For each class that opCode belongs to, check if there are too many
1431   // instructions of that class.
1432   // 
1433   const InstrSchedClass sc = S.schedInfo.getSchedClass(opCode);
1434   return (S.getNumChoicesInClass(sc) == S.schedInfo.getMaxIssueForClass(sc));
1435 }
1436
1437
1438 //************************* External Functions *****************************/
1439
1440
1441 //---------------------------------------------------------------------------
1442 // Function: ViolatesMinimumGap
1443 // 
1444 // Purpose:
1445 //   Check minimum gap requirements relative to instructions scheduled in
1446 //   previous cycles.
1447 //   Note that we do not need to consider `nextEarliestIssueTime' here because
1448 //   that is also captured in the earliest start times for each opcode.
1449 //---------------------------------------------------------------------------
1450
1451 static inline bool
1452 ViolatesMinimumGap(const SchedulingManager& S,
1453                    MachineOpCode opCode,
1454                    const cycles_t inCycle)
1455 {
1456   return (inCycle < S.getEarliestStartTimeForOp(opCode));
1457 }
1458
1459
1460 //---------------------------------------------------------------------------
1461 // Function: instrIsFeasible
1462 // 
1463 // Purpose:
1464 //   Check if any issue restrictions would prevent the instruction from
1465 //   being issued in the current cycle
1466 //---------------------------------------------------------------------------
1467
1468 bool
1469 instrIsFeasible(const SchedulingManager& S,
1470                 MachineOpCode opCode)
1471 {
1472   // skip the instruction if it cannot be issued due to issue restrictions
1473   // caused by previously issued instructions
1474   if (ViolatesMinimumGap(S, opCode, S.getTime()))
1475     return false;
1476   
1477   // skip the instruction if it cannot be issued due to issue restrictions
1478   // caused by previously chosen instructions for the current cycle
1479   if (ConflictsWithChoices(S, opCode))
1480     return false;
1481   
1482   return true;
1483 }
1484
1485 //---------------------------------------------------------------------------
1486 // Function: ScheduleInstructionsWithSSA
1487 // 
1488 // Purpose:
1489 //   Entry point for instruction scheduling on SSA form.
1490 //   Schedules the machine instructions generated by instruction selection.
1491 //   Assumes that register allocation has not been done, i.e., operands
1492 //   are still in SSA form.
1493 //---------------------------------------------------------------------------
1494
1495 namespace {
1496   class InstructionSchedulingWithSSA : public FunctionPass {
1497     const TargetMachine &target;
1498   public:
1499     inline InstructionSchedulingWithSSA(const TargetMachine &T) : target(T) {}
1500
1501     const char *getPassName() const { return "Instruction Scheduling"; }
1502   
1503     // getAnalysisUsage - We use LiveVarInfo...
1504     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1505       AU.addRequired<FunctionLiveVarInfo>();
1506     }
1507     
1508     bool runOnFunction(Function &F);
1509   };
1510 } // end anonymous namespace
1511
1512
1513 bool InstructionSchedulingWithSSA::runOnFunction(Function &F)
1514 {
1515   if (SchedDebugLevel == Sched_Disable)
1516     return false;
1517   
1518   SchedGraphSet graphSet(&F, target);   
1519   
1520   if (SchedDebugLevel >= Sched_PrintSchedGraphs)
1521     {
1522       cerr << "\n*** SCHEDULING GRAPHS FOR INSTRUCTION SCHEDULING\n";
1523       graphSet.dump();
1524     }
1525   
1526   for (SchedGraphSet::const_iterator GI=graphSet.begin(), GE=graphSet.end();
1527        GI != GE; ++GI)
1528     {
1529       SchedGraph* graph = (*GI);
1530       const vector<const BasicBlock*> &bbvec = graph->getBasicBlocks();
1531       assert(bbvec.size() == 1 && "Cannot schedule multiple basic blocks");
1532       const BasicBlock* bb = bbvec[0];
1533       
1534       if (SchedDebugLevel >= Sched_PrintSchedTrace)
1535         cerr << "\n*** TRACE OF INSTRUCTION SCHEDULING OPERATIONS\n\n";
1536       
1537       // expensive!
1538       SchedPriorities schedPrio(&F, graph,getAnalysis<FunctionLiveVarInfo>());
1539       SchedulingManager S(target, graph, schedPrio);
1540           
1541       ChooseInstructionsForDelaySlots(S, bb, graph); // modifies graph
1542       
1543       ForwardListSchedule(S);               // computes schedule in S
1544       
1545       RecordSchedule(bb, S);                // records schedule in BB
1546     }
1547   
1548   if (SchedDebugLevel >= Sched_PrintMachineCode)
1549     {
1550       cerr << "\n*** Machine instructions after INSTRUCTION SCHEDULING\n";
1551       MachineCodeForMethod::get(&F).dump();
1552     }
1553   
1554   return false;
1555 }
1556
1557
1558 Pass *createInstructionSchedulingWithSSAPass(const TargetMachine &tgt) {
1559   return new InstructionSchedulingWithSSA(tgt);
1560 }