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