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