lib/Target/SparcV9/InstrSched/InstrScheduling.cpp

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